LeetCode 30. Substring with Concatenation of All Words [Hard] [C++] 解題筆記

這題給我們一個 string s 和一些等長 words，要我們求出 s 中所有可以由所有 words 組合形成的子串。

EX:

        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.

想法:

    這題使用 HashMap 紀錄所有 word 出現的次數，然後遍歷 s ，以每個 char 作為子串開頭檢查是否可以形成

包含所有 words 的子串。

    另外這題似乎有 O(n) 的解法，但太複雜了感覺很難想到。

完整程式碼:

解法一:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if (s.empty() || words.empty()) { return {}; }
        vector<int> res;
        unordered_map<string, int> word_cnt;
        for (int i = 0; i < words.size(); i++) {
            word_cnt[words[i]]++;
        }
        int n = words.size();
	// all string in word have same length
        int len = words[0].size();
        for (int i = 0; i <= (int)s.size() - n*len; i++) {
            unordered_map<string, int> s_cnt;
            int j = 0;
            // iterate all words
            for (j; j < n; j++) {
                string tmp = s.substr(i + j *len, len);
                if (word_cnt.find(tmp) == word_cnt.end()) { break; }
                if (s_cnt[tmp] >= word_cnt[tmp]) { break; }
                s_cnt[tmp]++;
            }
            if (j == n) {
                res.emplace_back(i);
            }
        }
        
        return res;
    }
};

解法二(string_view):

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if (s.empty() || words.empty()) { return {}; }
        int n = words.size();
        int len = words[0].length();
        if (n*len > s.length()) { return {}; }
        vector<int> res;
        unordered_map<string_view, int> word_cnt;
        /*for (int i = 0; i < words.size(); i++) {
            word_cnt[string_view(words[i])]++;
        }*/
        for (const string& word : words) {
            word_cnt[string_view(word)]++;
        }
       
        string_view view_only(s);
        for (int i = 0; i <= (int)view_only.length() - n*len; i++) {
            unordered_map<string_view, int> s_cnt;
            int j = 0;
            // iterate all words
            for (j; j < n; j++) {
                string_view tmp = view_only.substr(i + j *len, len);
                auto it = word_cnt.find(tmp);
                if (it == word_cnt.end()) { break; }
                if (s_cnt[tmp] >= it->second) { break; }
                s_cnt[tmp]++;
            }
            if (j == n) {
                res.push_back(i);
            }
        }
        
        return res;
    }
};