Hash Table

242. Valid Anagram

242. Valid Anagram Anagram 有一個特性就是只要是 Anagram 每個字元的字數都會一樣多,因此一個解法是先計算出一個單字每個字元所出現的次數,接著是再見去另外一個單字,有出現的字元的字數。 如果中間有發現其他的字元,就代表不是 Anagram 。 最後還要再記得檢查,有沒有哪個字元有在第一個單字有出現,但是第二個單字沒有出現。 {% tabs %} {% tab title="Python" %} class Solution: def isAnagram(self, s: str, t: str) -> bool: table = defaultdict(int) for char in s: table[char] += 1 for char in t: if table[char] > 0: table[
Gary Lai

560. Subarray Sum Equals K

560. Subarray Sum Equals K 給定一個陣列,要找一個子陣列的總和為 K 。 暴力法 我想到的方法是我先算出每個位置的 prefix sum ,之後我就看如果當前這個位置的 prefix sum 減掉前面某一個位置的 prefix sum ,如果說當好等於 k ,就代表這兩個位置之間的總和是 k ,也就是說前一個位置到當前這個位置的子陣列的總和是 k 。 有一個邊角情況要考慮,那就是第一個元素可能剛好就是 k ,所以我們的 prefix_sum 陣列前面要多放一個零的元素。這樣剛好第一個元素就是一個子陣列滿足總和是 k 。 先從 [1..l] 算出 prefix sum 。 接著從 [i..l-1] 開始,設定起始位置,然後看看從 [i+1..l] 是不是有兩個位置之間的差剛好是 k
Gary Lai

49. Group Anagrams

49. Group Anagrams Anagram 的特性就是裡面的每個字元出現的頻率相同,如果經過排序的話,只要是 Anagram 就一定會一樣。 利用這個特性,我們將每個詞都排序過,當作 key ,在 Hash table 裡面去把每個 anagram 加到那個 arrary 裡面。 class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: table = defaultdict(list) for s in strs: table[tuple(sorted(s))].append(s) return table.values()
Gary Lai