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

遍歷s中所有長(zhǎng)度為 nxlen 的子串，當(dāng)剩余子串的長(zhǎng)度小于 nxlen 時(shí)，就不用再判斷了。所以i從0開始，到 (int)s.size() - nxlen 結(jié)束就可以了，注意這里一定要將 s.size() 先轉(zhuǎn)為整型數(shù)，再進(jìn)行解法。一定要形成這樣的習(xí)慣，一旦 size() 后面要減去數(shù)字時(shí)，先轉(zhuǎn)為 int 型，因?yàn)?size() 的返回值是無符號(hào)型，一旦減去一個(gè)比自己大的數(shù)字，則會(huì)出錯(cuò)。對(duì)于每個(gè)遍歷到的長(zhǎng)度為 nxlen 的子串，需要驗(yàn)證其是否剛好由 words 中所有的單詞構(gòu)成，檢查方法就是每次取長(zhǎng)度為 len 的子串，看其是否是 words 中的單詞。為了方便比較，建立另一個(gè) HashMap，當(dāng)取出的單詞不在 words 中，直接 break 掉，否則就將其在新的 HashMap 中的映射值加1，還要檢測(cè)若其映射值超過原 HashMap 中的映射值，也 break 掉，因?yàn)榫退惝?dāng)前單詞在 words 中，但若其出現(xiàn)的次數(shù)超過 words 中的次數(shù)，還是不合題意的。在 for 循環(huán)外面，若j正好等于n，說明檢測(cè)的n個(gè)長(zhǎng)度為 len 的子串都是 words 中的單詞，并且剛好構(gòu)成了 words，則將當(dāng)前位置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í)間復(fù)雜度的解法，設(shè)計(jì)思路非常巧妙，但是感覺很難想出來，博主目測(cè)還未到達(dá)這種水平。這種方法不再是一個(gè)字符一個(gè)字符的遍歷，而是一個(gè)詞一個(gè)詞的遍歷，比如根據(jù)題目中的例子，字符串s的長(zhǎng)度n為 18，words 數(shù)組中有兩個(gè)單詞 (cnt=2)，每個(gè)單詞的長(zhǎng)度 len 均為3，那么遍歷的順序?yàn)?0，3，6，8，12，15，然后偏移一個(gè)字符 1，4，7，9，13，16，然后再偏移一個(gè)字符 2，5，8，10，14，17，這樣就可以把所有情況都遍歷到，還是先用一個(gè) HashMap m1 來記錄 words 里的所有詞，然后從0開始遍歷，用 left 來記錄左邊界的位置，count 表示當(dāng)前已經(jīng)匹配的單詞的個(gè)數(shù)。然后一個(gè)單詞一個(gè)單詞的遍歷，如果當(dāng)前遍歷的到的單詞t在 m1 中存在，那么將其加入另一個(gè) HashMap m2 中，如果在 m2 中個(gè)數(shù)小于等于 m1 中的個(gè)數(shù)，那么 count 自增1，如果大于了，則需要做一些處理，比如下面這種情況：s = barfoofoo, words = {bar, foo, abc}，給 words 中新加了一個(gè) abc ，目的是為了遍歷到 barfoo 不會(huì)停止，當(dāng)遍歷到第二 foo 的時(shí)候,  m2[foo]=2, 而此時(shí) m1[foo]=1，這時(shí)候已經(jīng)不連續(xù)了，所以要移動(dòng)左邊界 left 的位置，先把第一個(gè)詞 t1=bar 取出來，然后將 m2[t1] 自減1，如果此時(shí) m2[t1]<m1[t1] 了，說明一個(gè)匹配沒了，那么對(duì)應(yīng)的 count 也要自減1，然后左邊界加上個(gè) len，這樣就可以了。如果某個(gè)時(shí)刻 count 和 cnt 相等了，說明成功匹配了一個(gè)位置，將當(dāng)前左邊界 left 存入結(jié)果 res 中，此時(shí)去掉最左邊的一個(gè)詞，同時(shí) count 自減1，左邊界右移 len，繼續(xù)匹配。如果匹配到一個(gè)不在 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++實(shí)現(xiàn)LeetCode(30.串聯(lián)所有單詞的子串)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)串聯(lián)所有單詞的子串內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論