今天小編給大家分享一下C++怎么實(shí)現(xiàn)串聯(lián)所有單詞的子串的相關(guān)知識(shí)點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識(shí)，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來(lái)了解一下吧。

創(chuàng)新互聯(lián)公司是專業(yè)的安定網(wǎng)站建設(shè)公司，安定接單;提供網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè),網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行安定網(wǎng)站開發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!

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)所有單詞的子串，就是說(shuō)給定一個(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 來(lái)建立所有的單詞和其出現(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() 的返回值是無(wú)符號(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è)若其映射值超過(guò)原 HashMap 中的映射值，也 break 掉，因?yàn)榫退惝?dāng)前單詞在 words 中，但若其出現(xiàn)的次數(shù)超過(guò) words 中的次數(shù)，還是不合題意的。在 for 循環(huán)外面，若j正好等于n，說(shuō)明檢測(cè)的n個(gè)長(zhǎng)度為 len 的子串都是 words 中的單詞，并且剛好構(gòu)成了 words，則將當(dāng)前位置i加入結(jié)果 res 即可，具體參見(jiàn)代碼如下：

解法一：

class Solution {
public:
    vector findSubstring(string s, vector& words) {
        if (s.empty() || words.empty()) return {};
        vector res;
        int n = words.size(), len = words[0].size();
        unordered_map wordCnt;
        for (auto &word : words) ++wordCnt[word];
        for (int i = 0; i <= (int)s.size() - n * len; ++i) {
            unordered_map 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ì)思路非常巧妙，但是感覺(jué)很難想出來(lái)，博主目測(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 來(lái)記錄 words 里的所有詞，然后從0開始遍歷，用 left 來(lái)記錄左邊界的位置，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 取出來(lái)，然后將 m2[t1] 自減1，如果此時(shí) m2[t1]

解法二：

class Solution {
public:
    vector findSubstring(string s, vector& words) {
        if (s.empty() || words.empty()) return {};
        vector res;
        int n = s.size(), cnt = words.size(), len = words[0].size();
        unordered_map m1;
        for (string w : words) ++m1[w];
        for (int i = 0; i < len; ++i) {
            int left = i, count = 0;
            unordered_map 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++怎么實(shí)現(xiàn)串聯(lián)所有單詞的子串”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會(huì)為大家更新不同的知識(shí)，如果還想學(xué)習(xí)更多的知識(shí)，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。