205. 同構字符串
- 思路
- example
- 假設：t.length == s.length
- 不改變字符的順序
hash[s[i]] = 對應的t中的字符 （可能是t[i]也可能是之前t中的字符）
- 復雜度. 時間：O(n), 空間: O(n)
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
hash_s = collections.defaultdict(str)
hash_t = collections.defaultdict(str)
for i in range(len(s)):
ch1, ch2 = s[i], t[i]
# map
if ch1 not in hash_s:
hash_s[ch1] = ch2
if ch2 not in hash_t:
hash_t[ch2] = ch1
# compare
if hash_s[ch1] != ch2 or hash_t[ch2] != ch1:
return False
return True
- 單個字典不夠
- s='badc', t='baba'
- s = 'ab', t='ca' (True)
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
m, n = len(s), len(t)
if m != n:
return False
table = collections.defaultdict(str)
for i in range(m):
if s[i] != t[i]:
if s[i] not in table:
table[s[i]] = t[i]
else:
if table[s[i]] != t[i]:
return False
return True
- 這個可以
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
m, n = len(s), len(t)
if m != n:
return False
table_s = collections.defaultdict(str)
table_t = collections.defaultdict(str)
for i in range(m):
ch1, ch2 = s[i], t[i]
if ch1 not in table_s:
table_s[ch1] = ch2
if ch2 not in table_t:
table_t[ch2] = ch1
if table_s[ch1] != ch2 or table_t[ch2] != ch1:
return False
return True
1002. 查找共用字符
- 思路
- example
- xxx
ord('a')
chr(ord('a'))
-
復雜度. 時間：O(?), 空間: O(?)
class Solution:
def commonChars(self, words: List[str]) -> List[str]:
table = [0] * 26
n = len(words)
for ch in words[0]:
table[ord(ch) - ord('a')] += 1
for i in range(1, n):
word = words[i]
table2 = [0] * 26
for ch in word:
table2[ord(ch) - ord('a')] += 1
for j in range(26):
table[j] = min(table[j], table2[j]) # j對應字符出現(xiàn)在最小次數(shù)
# 當前遍歷到的word中不出現(xiàn)的字符必為0
res = []
for j in range(26):
if table[j] != 0: # 必為共用字符, 重復次數(shù)：table[j]
res.extend([chr(j + ord('a'))] * table[j])
return res
class Solution:
def commonChars(self, words: List[str]) -> List[str]:
n = len(words)
res = []
table = collections.defaultdict(int)
for ch in words[0]:
table[ch] += 1
for i in range(1, n):
table2 = collections.defaultdict(int)
for ch in words[i]:
table2[ch] += 1
for j in range(26): # !!!
ch = chr(j + ord('a'))
table[ch] = min(table[ch], table2[ch])
for key, val in table.items():
if val != 0: # 注意duplicate情況
res.extend([key] * val)
return res
- 去重版本
- 數(shù)組
- set 去重刻撒， 每個word重設
- ans = ['e', 'l']
class Solution:
def commonChars(self, words: List[str]) -> List[str]:
table = [0] * 26
n = len(words)
for i in range(n):
word = words[i]
temp = set()
for ch in word:
if ch not in temp:
table[ord(ch) - ord('a')] += 1
temp.add(ch)
res = []
for j in range(26):
if table[j] == n:
res.append(chr(j + ord('a')))
return res
- 以下版本不正確
class Solution:
def commonChars(self, words: List[str]) -> List[str]:
n = len(words)
res = []
table = collections.defaultdict(int)
for ch in words[0]:
if table[ch] < 1:
table[ch] += 1
for i in range(1, n):
for ch in words[i]:
if table[ch] < i+1:
table[ch] += 1
for key, val in table.items():
if val == n:
res.append(key)
return res
