383. Ransom Note

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

種類 : hash table
難度 : medium
題目 : 383. Ransom Note

思維邏輯

  1. 將四個list轉為set(❌錯誤)

    1. 歷遍四個set

  2. 歷遍前兩個list，將和與次數紀錄在dict

    1. 歷遍後兩個list，若兩元素相加 * -1在dict中，count += dict[元素相加*-1]

解法

1
2
3
4
5
6
7
8
9
10
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        note = [0] * 26
        for i in magazine:
            note[ord(i)-ord('a')] += 1
        for i in ransomNote:
            note[ord(i)-ord('a')] -= 1
            if note[ord(i)-ord('a')] < 0:
                return False
        return True

ransomNote長度: m
magazine長度: n
時間複雜度: O(m+n)
空間複雜度: O(1)

難點

  1. ransomNote與magazine混肴先後關係順序

最佳解法

此為最佳解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
"""
字典
數據量大時，使用list優於dict
"""
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        counts = {}
        for c in magazine:
            counts[c] = counts.get(c, 0) + 1
        for c in ransomNote:
            if c not in counts or counts[c] == 0:
                return False
            counts[c] -= 1
        return True

時間複雜度: O(m+n)
空間複雜度: O(m+n)