怎么用C++串聯(lián)所有單詞的子串

這篇文章主要介紹“怎么用C++串聯(lián)所有單詞的子串”的相關(guān)知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“怎么用C++串聯(lián)所有單詞的子串”文章能幫助大家解決問題。

創(chuàng)新互聯(lián)是一家以成都網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計、品牌設(shè)計、軟件運維、成都網(wǎng)站營銷、小程序App開發(fā)等移動開發(fā)為一體互聯(lián)網(wǎng)公司。已累計為玻璃鋼雕塑等眾行業(yè)中小客戶提供優(yōu)質(zhì)的互聯(lián)網(wǎng)建站和軟件開發(fā)服務(wù)。

串聯(lián)所有單詞的子串

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ù)組可能有重復(fù)單詞，就要用 HashMap 來建立所有的單詞和其出現(xiàn)次數(shù)之間的映射，即統(tǒng)計每個單詞出現(xiàn)的次數(shù)。

遍歷s中所有長度為 nxlen 的子串，當剩余子串的長度小于 nxlen 時，就不用再判斷了。所以i從0開始，到 (int)s.size() - nxlen 結(jié)束就可以了，注意這里一定要將 s.size() 先轉(zhuǎn)為整型數(shù)，再進行解法。一定要形成這樣的習(xí)慣，一旦 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) 時間復(fù)雜度的解法，設(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++串聯(lián)所有單詞的子串”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點。

網(wǎng)頁題目：怎么用C++串聯(lián)所有單詞的子串
文章分享：http://bm7419.com/article10/pscsgo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、標簽優(yōu)化、網(wǎng)站內(nèi)鏈、網(wǎng)站改版、定制開發(fā)、小程序開發(fā)

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容