[LeetCode] 30. Substring with Concatenation of All Words 串聯(lián)所有單詞的子串

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" 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: []

這道題讓我們求串聯(lián)所有單詞的子串，就是說給定一個長字符串，再給定幾個長度相同的單詞，讓找出串聯(lián)給定所有單詞的子串的起始位置，還是蠻有難度的一道題。假設(shè) words 數(shù)組中有n個單詞，每個單詞的長度均為 len，那么實際上這道題就讓我們出所有長度為 nxlen 的子串，使得其剛好是由 words 數(shù)組中的所有單詞組成。那么就需要經(jīng)常判斷s串中長度為 len 的子串是否是 words 中的單詞，為了快速的判斷，可以使用 HashMap，同時由于 words 數(shù)組可能有重復單詞，就要用 HashMap 來建立所有的單詞和其出現(xiàn)次數(shù)之間的映射，即統(tǒng)計每個單詞出現(xiàn)的次數(shù)。

遍歷s中所有長度為 nxlen 的子串，當剩余子串的長度小于 nxlen 時，就不用再判斷了。所以i從0開始，到 (int)s.size() - nxlen 結(jié)束就可以了，注意這里一定要將 s.size() 先轉(zhuǎn)為整型數(shù)，再進行解法。一定要形成這樣的習慣，一旦 size() 后面要減去數(shù)字時，先轉(zhuǎn)為 int 型，因為 size() 的返回值是無符號型，一旦減去一個比自己大的數(shù)字，則會出錯。對于每個遍歷到的長度為 nxlen 的子串，需要驗證其是否剛好由 words 中所有的單詞構(gòu)成，檢查方法就是每次取長度為 len 的子串，看其是否是 words 中的單詞。為了方便比較，建立另一個 HashMap，當取出的單詞不在 words 中，直接 break 掉，否則就將其在新的 HashMap 中的映射值加1，還要檢測若其映射值超過原 HashMap 中的映射值，也 break 掉，因為就算當前單詞在 words 中，但若其出現(xiàn)的次數(shù)超過 words 中的次數(shù)，還是不合題意的。在 for 循環(huán)外面，若j正好等于n，說明檢測的n個長度為 len 的子串都是 words 中的單詞，并且剛好構(gòu)成了 words，則將當前位置i加入結(jié)果 res 即可，具體參見代碼如下：

解法一：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if (s.empty() || words.empty()) return {};
        vector<int> res;
        int n = words.size(), len = words[0].size();
        unordered_map<string, int> wordCnt;
        for (auto &word : words) ++wordCnt[word];
        for (int i = 0; i <= (int)s.size() - n * len; ++i) {
            unordered_map<string, int> strCnt;
            int j = 0; 
            for (j = 0; j < n; ++j) {
                string t = s.substr(i + j * len, len);
                if (!wordCnt.count(t)) break;
                ++strCnt[t];
                if (strCnt[t] > wordCnt[t]) break;
            }
            if (j == n) res.push_back(i);
        }
        return res;
    }
};

這道題還有一種 O(n) 時間復雜度的解法，設(shè)計思路非常巧妙，但是感覺很難想出來，博主目測還未到達這種水平。這種方法不再是一個字符一個字符的遍歷，而是一個詞一個詞的遍歷，比如根據(jù)題目中的例子，字符串s的長度n為 18，words 數(shù)組中有兩個單詞 (cnt=2)，每個單詞的長度 len 均為3，那么遍歷的順序為 0，3，6，8，12，15，然后偏移一個字符 1，4，7，9，13，16，然后再偏移一個字符 2，5，8，10，14，17，這樣就可以把所有情況都遍歷到，還是先用一個 HashMap m1 來記錄 words 里的所有詞，然后從0開始遍歷，用 left 來記錄左邊界的位置，count 表示當前已經(jīng)匹配的單詞的個數(shù)。然后一個單詞一個單詞的遍歷，如果當前遍歷的到的單詞t在 m1 中存在，那么將其加入另一個 HashMap m2 中，如果在 m2 中個數(shù)小于等于 m1 中的個數(shù)，那么 count 自增1，如果大于了，則需要做一些處理，比如下面這種情況：s = barfoofoo, words = {bar, foo, abc}，給 words 中新加了一個 abc ，目的是為了遍歷到 barfoo 不會停止，當遍歷到第二 foo 的時候,  m2[foo]=2, 而此時 m1[foo]=1，這時候已經(jīng)不連續(xù)了，所以要移動左邊界 left 的位置，先把第一個詞 t1=bar 取出來，然后將 m2[t1] 自減1，如果此時 m2[t1]<m1[t1] 了，說明一個匹配沒了，那么對應(yīng)的 count 也要自減1，然后左邊界加上個 len，這樣就可以了。如果某個時刻 count 和 cnt 相等了，說明成功匹配了一個位置，將當前左邊界 left 存入結(jié)果 res 中，此時去掉最左邊的一個詞，同時 count 自減1，左邊界右移 len，繼續(xù)匹配。如果匹配到一個不在 m1 中的詞，說明跟前面已經(jīng)斷開了，重置 m2，count 為0，左邊界 left 移到 j+len，參見代碼如下：

解法二：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if (s.empty() || words.empty()) return {};
        vector<int> res;
        int n = s.size(), cnt = words.size(), len = words[0].size();
        unordered_map<string, int> m1;
        for (string w : words) ++m1[w];
        for (int i = 0; i < len; ++i) {
            int left = i, count = 0;
            unordered_map<string, int> m2;
            for (int j = i; j <= n - len; j += len) {
                string t = s.substr(j, len);
                if (m1.count(t)) {
                    ++m2[t];
                    if (m2[t] <= m1[t]) {
                        ++count;
                    } else {
                        while (m2[t] > m1[t]) {
                            string t1 = s.substr(left, len);
                            --m2[t1];
                            if (m2[t1] < m1[t1]) --count;
                            left += len;
                        }
                    }
                    if (count == cnt) {
                        res.push_back(left);
                        --m2[s.substr(left, len)];
                        --count;
                        left += len;
                    }
                } else {
                    m2.clear();
                    count = 0;
                    left = j + len;
                }
            }
        }
        return res;
    }
};

到此這篇關(guān)于C++實現(xiàn)LeetCode(30.串聯(lián)所有單詞的子串)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)串聯(lián)所有單詞的子串內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論