205. 同構(gòu)字符串

• 思路
  • example
  • 假設(shè)：t.length == s.length
  • 不改變字符的順序

hash[s[i]] = 對(duì)應(yīng)的t中的字符 （可能是t[i]也可能是之前t中的字符）

• 復(fù)雜度. 時(shí)間：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  

• 單個(gè)字典不夠
  • 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 

• 這個(gè)可以

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'))

• 復(fù)雜度. 時(shí)間：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對(duì)應(yīng)字符出現(xiàn)在最小次數(shù)
                # 當(dāng)前遍歷到的word中不出現(xiàn)的字符必為0
        res = []
        for j in range(26):
            if table[j] != 0: # 必為共用字符, 重復(fù)次數(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 去重， 每個(gè)word重設(shè)
  • 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