LeetCode Digest
4 分鐘 閱讀文 (大約 616 個字)

844. Backspace String Compare

題目
這邊記錄自己答案的演變和檢討，有需要的也可以直接跳到最後的 O(1) space complexity 解答

一開始的思路：用遞增的 index 同時 go through 這兩個字串，按照裡面的 backspace hint build 出兩個新的字串再來看看是否相等

繼續閱讀
LeetCode Digest
3 分鐘 閱讀文 (大約 375 個字)

438. Find All Anagrams in a String

題目
思路：怎麼判斷兩個字串是不是 anagram?

  • 可以把兩個字串都做排序，再看看是否相等，但這樣每次都要多花 O(n) 時間
  • 可以計算每個字母出現的頻率，再看看兩個字串的計算結果是否相等。雖然單獨算也是要 O(n)，但假如搭配 sliding window 移動的時候一個個字母加入計算，就不會有額外的時間複雜度
繼續閱讀
LeetCode Digest
3 分鐘 閱讀文 (大約 422 個字)

409. Longest Palindrome

題目
思路

  1. 怎麼判斷一個 string 是否為 palindrome？
    • (x) 做一個倒過來的 string 看看兩個是否相等
      • 需要 O(n) 時間複雜度，太長了，因為你必須對所有的字串組合做測試
    • (o) Palindrome 一定是由偶數個數的字母組成，頂多再加上一組奇數個數的字母
  2. 先用 dict 記錄每個 character 的個數，再利用計算完成的 dict 來算出答案
繼續閱讀
LeetCode Digest
2 分鐘 閱讀文 (大約 303 個字)

Isomorphic Strings

題目
這題看似不難，但第一次的做法錯了，第一次的程式碼如下，想法是用 mapping 組一個新字串 t2，假如跟 t 相同就 return True

Python 3 wrong solution:

1
2
3
4
5
6
7
8
def isIsomorphic(self, s: str, t: str) -> bool:
    d = {}
    for i in range(len(s)):
        d[s[i]] = t[i]
    t2 = ''
    for c in s:
        t2 += d[c]
    return t == t2
繼續閱讀

分類

標籤雲

android array authentication binary search binary search tree binary tree bit manipulation breadth-first search database depth-first search distributed system django docker dokku dynamic programming graph greedy hash table heap heroku java jwt linked list matrix mysql paas package management pipenv postgresql python recursion shortest path simulation sliding window sorting stack string tree two pointers

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×