LeetCode
C++
You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.
You can return the answer in any order.
Example 1:
Example 2:
Example 3:
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
s and words[i] consist of lowercase English letters.
這題子字串我們使用的解題方式是slide window,並且用雙指針實現。
首先,我們需要hashmap去記錄當前所有子字串還未被使用的次數,因此開頭先由一個迴圈將word中所有可用的字都記錄進去。
接下來檢查字串的部分,window的寬度跟子字串寬度相同,一次向右移動一個字元。
假設子字串長度為3,s的長度為24,我們第一次檢查的index是0,3,6,9,12,15,18,21,第二次檢查的index就是1,4,7,10,13,16,19,以此類推,剩餘長度不足子字串長度時終止,
每當檢查到一個合法子字串,就將hashmap中相應的值-1,同時,如果hashmap中,該子字串剩餘可用次數>=0時,代表我們沒有用超過可用次數,因此紀錄合法子字串的變數count要+1。
每次迭代中,若是檢查到window的寬度過大,就要將左指針向右移。因此,右移過程中丟到的子字串,也要將相應hashmap中使用次數+1回去,同時,若是剩餘使用次數大於0,代表還沒滿足將所有子字串都使用的條件,因此count要-1。
最後一直迭代到count與words中合法子字串的數量相同,就代表這是一個合法組合,紀錄該組合的起始index,放進vector中統一回傳。