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对应字符出现在最小次数
# 当前遍历到的word中不出现的字符必为0
res = []
for j in range(26):
if table[j] != 0: # 必为共用字符, 重复次数：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
- 去重版本
- 数组
- 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
