1002. Find Common Characters

發表於 分類於 ， 閱讀次數： 文章字數： 1.3k

種類 : hash table
難度 : easy
題目 : 1002. Find Common Characters

思維邏輯

  1. 使用list紀錄每一個word的字母頻率
  2. 取words中每個字母最小值
  3. 將字母頻率轉為輸出

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        letters_list = []
        for word in words:
            # initialize list
            letters = [0] * 26

            # count each letter
            for letter in word:
                letters[ord(letter) - ord('a')] += 1
            
            letters_list.append(letters)
        
        result_list = letters_list[0]
        # min each word
        for word in letters_list:
            for i in range(len(word)):
                result_list[i] = min(word[i], result_list[i])
        
        result = []
        for letter in range(len(result_list)):
            for _ in range(result_list[letter]):
                result.append(chr(ord('a') + letter))

        return result

word長度: m
時間複雜度: O(3mn) -> O(mn) -> O(n)
空間複雜度: O(1)

難點

  1. 取每個字母的最小值

最佳解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        if not words: return []
        result = []
        hash = [0] * 26 # 用来统计所有字符串里字符出现的最小频率
        for i, c in enumerate(words[0]):  # 用第一个字符串给hash初始化
            hash[ord(c) - ord('a')] += 1
        # 统计除第一个字符串外字符的出现频率
        for i in range(1, len(words)):
            hashOtherStr = [0] * 26
            for j in range(len(words[i])):
                hashOtherStr[ord(words[i][j]) - ord('a')] += 1
            # 更新hash，保证hash里统计26个字符在所有字符串里出现的最小次数
            for k in range(26):
                hash[k] = min(hash[k], hashOtherStr[k])
        # 将hash统计的字符次数，转成输出形式
        for i in range(26):
            while hash[i] != 0: # 注意这里是while，多个重复的字符
                result.extend(chr(i + ord('a')))
                hash[i] -= 1
        return result