從LeetCode學演算法 - 94 Hash Table (10)

0438. Find All Anagrams in a String (Easy)

Question

Given a string s and a ** non-empty** string ** p**, find all the start indices of ** p**’s anagrams in ** s**.

Strings consist of lowercase English letters only and the length of both strings s and ** p** will not be larger than 20,100.

The order of output does not matter.

Example 1

1
2
Input:
s: "cbaebabacd" p: "abc"

1
2
Output:
[0, 6]

1
2
3
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2

1
2
Input:
s: "abab" p: "ab"

1
2
Output:
[0, 1, 2]

1
2
3
4
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

分析/解題

給定一個字串s及一個非空的字串p，
試找出所有在p在s內的所有異位構詞(anagram)的起始的索引值。
本題當中的字串僅含小寫英文字母，且s和p的長度分別不會大於20, 100.
(但不用在意輸出的順序)

我們先前已經提過anagram的定義了，詳情可見0242. Valid Anagram (Easy) 。簡單來說，anagram是指說兩個字串是由相同的字元組成的，
只有順序可能不同而已。

我們先假設我們拿到兩個字串，要檢查它們是不是互為anagram，
端看它們的’a’出現的次數，’b’出現的次數，’c’出現的次數…,
‘z’出現的次數是否相同即可。
這個儲存兩者出現的次數，可以使用HashTable來計算，
而且由於我們要分的內容很簡單，所以只需要小寫字母個數26個即可，
也就是Java可以使用一個長度為26的一維陣列，
Python可以使用串列，要使用字典也行(相當於HashMap)。

回到我們的問題，我們想要在s當中找到一個子字串，
使得這個子字串和p互為anagram，
這時候應該可以先將p的各字母出現次數先行記錄下來。
接下來從s的index 0開始往右 ，一路計算走到可以取p的長度為止，
如果這段能和p的組成內容相同，那就可以記做其中一個解。

為了要比對是否組成內容相同，
我們可以將每次看到的字母從p的hash table中扣除掉 ，
當所有整個hash table都歸零的時候，我們就知道當前的組成相同了。
但為了不需要每次都檢查整個hash table，
我們可以先行設定一個cnt變數，其值等於p的長度。
每次碰到可以扣除的組成就將cnt遞減，
這樣當cnt為0且當前長度為和p長度相等時，就知道取得一個解了。

接下來，我們需要一個left和一個right的索引值來記錄。
由於長度固定就這麼長，當我們已經來到左右距離p的長度時，
我們可以將left和right各自往右移動一格 。
同時left移出

舉例來說假設：
s: “ecba ebabac d” p: “abc”
(這邊將Example 1前面多加一個字元比較容易看出不同)

(left, right, cnt) : (0, 0, 3) -> (0, 1, 3) -> (0, 2, 2) -> (0, 3, 1)
沿路會檢查’e’, ‘c’, ‘b’，每次碰到的字母會從p的hash table中扣掉，
不過cnt這樣只會降到1，表示沒有成立anagram 。
(left, right, cnt) : (0, 3, 1) -> (1, 4, 0)
將left往右移一格，’e’就出範圍外了(hash table要加回來)，
接著right往右移一格，’a’進入範圍內，且符合p的hash table擁有的子母，
所以cnt會從1降為0，同時範圍長度相符，
表示這是其中一個解，將1加入到我們的答案範圍中。
(left, right, cnt) : (1, 4, 0) -> (2, 5, 1) -> (3, 6, 2) -> (4, 7, 3)
依序移出範圍，如果發現加上去前hash table該值有≥0的話，
表示有移出p原有的字母，所以我們要將cnt進行遞增。
(left, right, cnt) : (4, 7, 3) -> (5, 8, 2) -> (6, 9, 1) -> (7, 10, 0)
同樣經歷了一個cnt等於0且長度等於p的範圍，
將7 加入答案當中。
(left, right, cnt) : (8, 11, 1) -> right超過，停止檢查。

所以按上面這個範例的output就會是[1, 7]。

這個題目由於我們中途開始的left和right呈現一個固定距離的狀態，
只是隨著遞增滑動，所以這種固定窗口大小並且移動的方式，
一般稱為Sliding Window 。
(也可以視為Two Pointer在某種狀態的條件限定)

依此，我們可以寫成程式碼如下：

Java

Java的部分，參考了一位leetcode上的解法，
我們使用一個ArrayList來儲存我們的答案，
並且前期的檢查可以分別檢查s, p是否為null或空，
以及s的長度不能小於p的長度才行(不然要怎麼組對吧XD)

接著，我們使用一個長度26的一維陣列，
也可以使用ASCII長度256直接存，我們使用26的長度時，
index使用c-’a’即可對應。

初始化left, right, count後，迴圈條件設定為right還沒有超出去範圍。
迴圈內的判斷式則利用++和–的特性，
(放後面時會先進行完整個操作才遞增/遞減)，
其他的重點做法跟前面的描述是一樣的，
讀者可以再自己嘗試在紙上推導一次，會更加清楚。

Python

Python的部分我們示範使用字典來處理，
由於我們不想要每次在取值時都先檢查值有沒有存在的問題，
(不論是get或者是用[]取值，字典都不會有預設值)
所以這邊先行將26個字母的對應都置入0，後續就不需要再檢查了。 其它的部分跟Java的寫法基本相同，只是沒有++跟- -能用而已XD!

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(1)，
空間複雜度如果要算上答案的部分的話則為O(N)，N為s的長度)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**