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

測出錯誤的 input:

1
2
s = "badc"
t = "baba"

錯誤點在於沒有檢查這個條件：No two characters may map to the same character

檢討如下：

  • 寫完要 run 之前應該最後 check 一次是否有滿足題目提到的所有條件
  • 以這題來說，比較好的做法是一個個 check 每個 character
    • 這樣只需跑一次 for-loop，不需要再跑第二次組一個新字串
    • 每個 character 都 check 就不會漏掉上面那個條件

修正解法如下

Python 3 solution:

1
2
3
4
5
6
7
8
9
10
11
def isIsomorphic(self, s: str, t: str) -> bool:
    mapping = {}
    for i in range(len(s)):
        if s[i] not in mapping:
            if t[i] in mapping.values():  # 一個 t 字母同時對應到兩個 s 字母
                return False
            mapping[s[i]] = t[i]
        else:
            if mapping[s[i]] != t[i]:  # 一個 s 字母同時對應到兩個 t 字母
                return False
    return True
# ,
Reverse Linked List
Binary Number with Alternating Bits

評論

分類

標籤雲

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

×