C C++算法題解LeetCode1408數(shù)組中的字符串匹配

更新時(shí)間：2022年10月14日 09:21:10 作者：Junkman丶

這篇文章主要為大家介紹了C C++算法題解LeetCode1408數(shù)組中的字符串匹配示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目描述

題目鏈接：1408. 數(shù)組中的字符串匹配

給你一個(gè)字符串?dāng)?shù)組 words ，數(shù)組中的每個(gè)字符串都可以看作是一個(gè)單詞。請(qǐng)你按任意順序返回 words 中是其他單詞的子字符串的所有單詞。

如果你可以刪除 words[j] 最左側(cè)和/或最右側(cè)的若干字符得到 word[i] ，那么字符串 words[i] 就是 words[j] 的一個(gè)子字符串。

提示:

示例 1：

輸入：words = ["mass","as","hero","superhero"]
輸出：["as","hero"]
解釋："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。
["hero","as"] 也是有效的答案。

示例 2：

輸入：words = ["leetcode","et","code"]
輸出：["et","code"]
解釋："et" 和 "code" 都是 "leetcode" 的子字符串。

示例 3：

輸入： words = ["blue","green","bu"]
輸出： []

整理題意

題目給定一個(gè)字符串?dāng)?shù)組 words，對(duì)于數(shù)組中的每個(gè)字符串來說，如果該字符串為數(shù)組中其他某個(gè)字符串的子串，那么就將該字符串加入答案字符串?dāng)?shù)組?？梢园凑杖我忭樞蚍祷卦摯鸢笖?shù)組。

解題思路分析

注意題目的數(shù)據(jù)提示：題目數(shù)據(jù) 保證每個(gè) words[i] 都是獨(dú)一無二的。所以不存在兩個(gè)相同的字符串，也避免了互為子字符串的情況。

根據(jù)題目數(shù)據(jù)范圍來看，完全可以采用較為暴力的方法來進(jìn)行解題，枚舉每個(gè)字符串作為子串，檢查是否為其他某個(gè)字符串的子串即可。

優(yōu)化

在字符串匹配的時(shí)候可以采用 KMP 字符串匹配算法來進(jìn)行優(yōu)化時(shí)間復(fù)雜度。

具體實(shí)現(xiàn)

對(duì)于字符串匹配部分可以調(diào)用 string 中的 find() 函數(shù)進(jìn)行匹配 t.find(p)（在字符串 t 中匹配字符串 p，也就是查找字符串 t 中是否包含字符串 p）：

此處需要用到 string 庫中的 find() 函數(shù)與 string::npos 參數(shù)；

string::npos 參數(shù)是一個(gè)常數(shù)，用來表示不存在的位置。

string 中 find() 返回值是子串的第一個(gè)字符在母串中的位置（下標(biāo)記錄），如果沒有找到，那么會(huì)返回一個(gè)特別的標(biāo)記 string::npos。

可以對(duì)字符串?dāng)?shù)組 words 進(jìn)行排序處理，這樣就可以從最短的字符串開始匹配，且每次往后遍歷匹配，因?yàn)榍懊娴淖址欢ǘ逃诋?dāng)前字符串。

在使用 KMP 字符串匹配算法時(shí)需要注意：

KMP 字符串匹配算法的核心思想是 遞歸回溯思想，當(dāng)匹配失敗時(shí)根據(jù) nxt 數(shù)組來進(jìn)行回溯跳轉(zhuǎn)；
nxt 數(shù)組表示模式串的子串的前綴和后綴相同的最長長度，這樣就可以在匹配的過程中如果遇到不匹配的字符，模式串用 nxt 數(shù)組進(jìn)行遞歸跳轉(zhuǎn)到最長符合的位置進(jìn)行繼續(xù)匹配，從而不需要目標(biāo)串進(jìn)行重復(fù)的往返匹配。
其中需要要注意的一個(gè)技巧是 nxt[0] = -1，在把 nxt 數(shù)組進(jìn)行向右偏移時(shí)，第 0 位的值，我們將其設(shè)成了 -1，這只是為了編程的方便，并沒有其他的意義。
還需要注意 nxt 數(shù)組的優(yōu)化，優(yōu)化后在回溯跳轉(zhuǎn)的時(shí)候會(huì)回溯跳轉(zhuǎn)到首次與當(dāng)前字符不一樣字符的位置，避免了跳轉(zhuǎn)到和當(dāng)前字符一樣的位置進(jìn)行重復(fù)判斷。
在實(shí)現(xiàn) getNext() 函數(shù)的時(shí)候需要注意 nxt 數(shù)組溢出問題，可以通過增加 nxt 數(shù)組大小，或減少 getNext() 函數(shù)中循環(huán)遍歷的次數(shù)來防止越界出現(xiàn)的運(yùn)行錯(cuò)誤。
需要注意在 getNext() 函數(shù)中 j 的初始化為 -1，但在 KMP() 函數(shù)中 j 的初始化為 0。

復(fù)雜度分析

代碼實(shí)現(xiàn)

暴力

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        // 新知識(shí)：string::npos
        vector<string> ans;
        ans.clear();
        // 雙重循環(huán)暴力尋找
        for(auto &word1 : words){
            int l1 = word1.length();
            for(auto &word2 : words){
                int l2 = word2.length();
                // 當(dāng) l2 大于 l1 時(shí) 并且可以在 w2 中找到 w1 時(shí)
                if(l1 < l2 && word2.find(word1) != string::npos){
                    ans.emplace_back(word1);
                    break;
                }
            }
        }
        return ans;
    }
};

暴力 + 優(yōu)化

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        sort(words.begin(), words.end(), [](string &a, string &b){
            return a.length() < b.length();
        });
        // 新知識(shí)：string::npos
        vector<string> ans;
        ans.clear();
        int n = words.size();
        // 雙重循環(huán)暴力尋找
        for(int i = 0; i < n; i++){
            int l1 = words[i].length();
            for(int j = i + 1; j < n; j++){
                int l2 = words[j].length();
                // 當(dāng) l2 大于 l1 時(shí) 并且可以在 w2 中找到 w1 時(shí)
                if(l1 < l2 && words[j].find(words[i]) != string::npos){
                    ans.emplace_back(words[i]);
                    break;
                }
            }
        }
        return ans;
    }
};

KMP

class Solution {
    void getNext(string &p, vector<int> &nxt){
        // 把PMT進(jìn)行向右偏移時(shí)，第0位的值，我們將其設(shè)成了-1，
        // 這只是為了編程的方便，并沒有其他的意義。
        nxt[0] = -1;
        int i = 0, j = -1;
        int len = p.length();
        // ★注意 nxt 數(shù)組越界
        while(i < len){
            // j = -1 或者 匹配成功
            if(j == -1 || p[i] == p[j]){
                // nxt[++i] = ++j; 未優(yōu)化前
                i++;
                j++;
                if(p[i] == p[j]) nxt[i] = nxt[j];
                else nxt[i] = j;
            }
            // 匹配失敗，回溯
            else{
                j = nxt[j];
            }
        }
    }
    bool kmp(string &t, string &p, vector<int> &nxt){
        // ★注意這里的 j = 0 不是 j = -1
        int i = 0, j = 0;
        int lent = t.length();
        int lenp = p.length();
        while(i < lent && j < lenp){
            if(j == -1 || t[i] == p[j]){
                ++i;
                ++j;
            }
            else j = nxt[j];
        }
        if(j == lenp) return true;
        return false;
    }
public:
    vector<string> stringMatching(vector<string>& words) {
        sort(words.begin(), words.end(), [](string a, string b){
            return a.length() < b.length();
        });
        vector<string> ans;
        ans.clear();
        vector<int> nxt;
        int n = words.size();
        for(int i = 0; i < n; i++){
            int len_p = words[i].length();
            // ★注意 nxt 數(shù)組溢出
            // 可以這里 len_p + 1 也可以 getNext 中 -1
            nxt.resize(len_p + 1);
            getNext(words[i], nxt);
            for(int j = i + 1; j < n; j++){
                if(kmp(words[j], words[i], nxt)){
                    ans.emplace_back(words[i]);
                    break;
                }
            }
        }
        return ans;
    }
};

總結(jié)

通過該題了解到了一個(gè)新的知識(shí)點(diǎn)：string::npos 參數(shù)用來表示不存在的位置。當(dāng) string 中 find() 函數(shù)沒有匹配成功時(shí)，那么就會(huì)返回這個(gè)參數(shù) string::npos。
同時(shí)通過該題復(fù)習(xí)了 KMP 字符串匹配算法的實(shí)現(xiàn)，在實(shí)現(xiàn)過程中需要注意 nxt 數(shù)組的大小，防止下標(biāo)越界的運(yùn)行錯(cuò)誤；同時(shí)還需要注意在 getNext() 函數(shù)中 j 的初始化為 -1，但在 KMP() 函數(shù)中 j 的初始化為 0。