C++實現LeetCode(30.串聯所有單詞的子串)

Posted on by

[LeetCode] 30. Substring with Concatenation of All Words 串聯所有單詞的子串

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: []

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

遍歷s中所有長度為 nxlen 的子串，當剩餘子串的長度小於 nxlen 時，就不用再判斷瞭。所以i從0開始，到 (int)s.size() – nxlen 結束就可以瞭，註意這裡一定要將 s.size() 先轉為整型數，再進行解法。一定要形成這樣的習慣，一旦 size() 後面要減去數字時，先轉為 int 型，因為 size() 的返回值是無符號型，一旦減去一個比自己大的數字，則會出錯。對於每個遍歷到的長度為 nxlen 的子串，需要驗證其是否剛好由 words 中所有的單詞構成，檢查方法就是每次取長度為 len 的子串，看其是否是 words 中的單詞。為瞭方便比較，建立另一個 HashMap，當取出的單詞不在 words 中，直接 break 掉，否則就將其在新的 HashMap 中的映射值加1，還要檢測若其映射值超過原 HashMap 中的映射值，也 break 掉，因為就算當前單詞在 words 中，但若其出現的次數超過 words 中的次數，還是不合題意的。在 for 循環外面，若j正好等於n，說明檢測的n個長度為 len 的子串都是 words 中的單詞，並且剛好構成瞭 words，則將當前位置i加入結果 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) 時間復雜度的解法，設計思路非常巧妙，但是感覺很難想出來，博主目測還未到達這種水平。這種方法不再是一個字符一個字符的遍歷，而是一個詞一個詞的遍歷，比如根據題目中的例子，字符串s的長度n為 18，words 數組中有兩個單詞 (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 表示當前已經匹配的單詞的個數。然後一個單詞一個單詞的遍歷，如果當前遍歷的到的單詞t在 m1 中存在，那麼將其加入另一個 HashMap m2 中，如果在 m2 中個數小於等於 m1 中的個數，那麼 count 自增1，如果大於瞭，則需要做一些處理，比如下面這種情況：s = barfoofoo, words = {bar, foo, abc}，給 words 中新加瞭一個 abc ，目的是為瞭遍歷到 barfoo 不會停止，當遍歷到第二 foo 的時候,  m2[foo]=2, 而此時 m1[foo]=1，這時候已經不連續瞭，所以要移動左邊界 left 的位置，先把第一個詞 t1=bar 取出來，然後將 m2[t1] 自減1，如果此時 m2[t1]<m1[t1] 瞭，說明一個匹配沒瞭，那麼對應的 count 也要自減1，然後左邊界加上個 len，這樣就可以瞭。如果某個時刻 count 和 cnt 相等瞭，說明成功匹配瞭一個位置，將當前左邊界 left 存入結果 res 中，此時去掉最左邊的一個詞，同時 count 自減1，左邊界右移 len，繼續匹配。如果匹配到一個不在 m1 中的詞，說明跟前面已經斷開瞭，重置 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;
    }
};

到此這篇關於C++實現LeetCode(30.串聯所有單詞的子串)的文章就介紹到這瞭,更多相關C++實現串聯所有單詞的子串內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：