Leetcode-30-Substring with Concatenation of All Words

題目

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

• For example, if words = [“ab”,”cd”,”ef”], then “abcdef”, “abefcd”, “cdabef”, “cdefab”, “efabcd”, and “efcdab” are all concatenated strings. “acdbef” is not a concatenated string because it is not the concatenation of any permutation of words.

Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

題目連結

Example 1

Input: s = "barfoothefoobarman", words = ["foo","bar"]

Output: [0,9]

Explanation:

The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.

Example 2

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

Output: []

Explanation:

There is no concatenated substring.

Example 3

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

Output: [6,9,12]

Explanation:

The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"].
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"].
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"].

解釋題目

題目會給一個 string array words，words 內的每個字串的長度都相同。

permutation words 的定義是words 內的每個字串任意排列，但字元之間不能任意排列。

• Ex: words = [“foo”,”bar”]
• permutation words = foobar, barfoo
• not permutation words = bafoor

題目還會給一個 string s，在 s 內找到所有 permutation words 的 起始位置。

思路

1. i 是左指針，記錄當前尋找的 permutation words 的 起始位置。
2. j 是右指針，尋找可能的答案。
3. Table 記錄 words 中，每個 string 出現的次數。
4. COUNT 記錄 words 中總共有幾個 string。

圖解

外層迴圈，設成 words[0].size() 的原因 :

程式主要邏輯 :

程式碼

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int N = words[0].size();
        int COUNT = words.size();
        vector<int> result;
        unordered_map<string, int> Table;
        for(auto word: words)
            Table[word]++;

        for(int start = 0; start < N; start++){ // 迴圈這樣設，可以覆蓋到所有例子，不懂可以看圖解
            int i = start; // 左指針
            int j = i; //右指針
            int count = 0;
            unordered_map<string, int> Map;

            while(j < s.size()){
                if(Table.find(s.substr(j, N)) == Table.end()){
                    j += N;
                    i = j;
                    Map.clear();
                    count = 0;
                }else if(Map[s.substr(j, N)] < Table[s.substr(j, N)]){
                    Map[s.substr(j, N)] += 1;
                    j += N;
                    count += 1;
                }else if(Map[s.substr(j, N)] == Table[s.substr(j, N)]){
                    Map[s.substr(i, N)] -= 1;
                    i += N;
                    count -= 1;
                }

                if(count == COUNT){
                    result.push_back(i);
                    Map[s.substr(i, N)] -= 1;
                    i += N;
                    count -= 1;
                }

            }

        }

        return result;
    }
};