Try   HackMD

Leetcode 解題速記 30. Substring with Concatenation of All Words

tags: 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:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

測資範圍:

  • 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中統一回傳。

程式碼:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        unordered_map<string, int> m1;
        int len = words[0].size();
        int n = s.length();
        int m = words.size();
        for (const string& it : words)
        {
            m1[it]++;
        }
        for (int i = 0; i < len; i++)
        {
            int count = 0;
            unordered_map<string, int> temp = m1;
            for (int j = i; j <= n - len; j += len)
            {
                string current = s.substr(j, len);
                temp[current]--;
                if (temp[current] >= 0)
                {
                    count++;
                }

                int pop_start = j - m * len;
                if (pop_start >= 0)
                {
                    string pop_word = s.substr(pop_start, len);
                    temp[pop_word]++;
                    if (temp[pop_word] > 0)
                    {
                        count--;
                    }
                }
                if (count == m)
                {
                    ans.push_back(pop_start + len);
                }
            }
        }
        return ans;
    }
};