前往
大廳
主題

LeetCode - 438. Find All Anagrams in a String 解題心得

Not In My Back Yard | 2022-08-07 12:00:22 | 巴幣 2 | 人氣 280

題目連結:


題目意譯:
給定兩字串 s 和 p,回傳一包含所有在 s 中 p 的易位構詞(Anagram)開頭索引值之陣列。你可以按任意順序回傳答案。

一個易位構詞為一字詞或片語藉由重新排列另一個相異的字詞或片語之單字所組成,其中每個原始字母都只會被使用恰好一次。

限制:
1 ≦ s.length, p.length ≦ 3 × 10 ^ 4
s 和 p 由小寫英文字母組成。



範例測資:
範例 1:
輸入: s = "cbaebabacd", p = "abc"
輸出: [0,6]
解釋:
開頭索引值 = 0 之子字串為 "cba",其為 "abc" 的一個易位構詞。
開頭索引值 = 6 之子字串為 "bac",其為 "abc" 的一個易位構詞。

範例 2:
輸入: s = "abab", p = "ab"
輸出: [0,1,2]
解釋:
開頭索引值 = 0 之子字串為 "ab",其為 "ab" 的一個易位構詞。
開頭索引值 = 1 之子字串為 "ba",其為 "ab" 的一個易位構詞。
開頭索引值 = 2 之子字串為 "ab",其為 "ab" 的一個易位構詞。


解題思維:
其實就是這題(窮舉所有 s 中長度 p.length 的子字串)然後搭配上滑動視窗(Sliding Window)的精神(如這題)來計算各個「相鄰」s 之子字串各個字母的出現數目。

然後看這些子字串與 p 的字母是否有一一對應(利用各種字母出現數目的統計來比較即可)。如果有則代表找到一個子字串為 p 的易位構詞,而該子字串的開頭索引值就是題目要的。將這些開頭索引值集結起來形成一陣列即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作