DEV Community

Cover image for 一个字符串匹配多个字符串
IQIUM
IQIUM

Posted on • Updated on

一个字符串匹配多个字符串

题目来源:392. 判断子序列 - 力扣

这个假如有多个字符串需要判断是否是字符串的子串

对于给定字符串t,给定待匹配字符串数组words,字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace""abcde"的一个子序列,而"aec"不是)。

这里主要看它的进阶问题:

如果有大量输入的 S,称作 S1, S2, ... , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?

对于这样情况下,我们不可能考虑10亿个依次进行比较,这样的效率太低而且会超时,可以借鉴KMP的思想,提前记录下一个字符出现的地方

举个例子, 比如对于字符串' abc'(前面添加一个空格,方便后续处理),a 出现的地方在下标为 1 的地方,c 出现在下标为 3 的地方。

那么如果我们后面找字符串 'ac',索引的顺序就变成了 1->3,提高了访问效率。

我们可以给字符串(后面我们称为t)建立一个索引二维数组dp,t.length * 26(26个英文字母)

vector<vector<int>> dp(length, vector<int>(26, 0));
Enter fullscreen mode Exit fullscreen mode

对于每个字符,我们从后往前遍历,这样很方便记录下一个字符出现的地方:

for (int i = 0; i < 26; ++i) {
    int nextPos = -1;
    for (int j = length - 1; j >= 0; --j) {
        dp[j][i] = nextPos;
        if (('a' + i) == t[j]) {
            nextPos = j;
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

这里dp[i][j] 代表的是当前字符距离下一个字符'a'+j 出现的位置

那么,对于我们待查找的字符串 s,只需要从index 开始查找,直到结束:

int index = 0;
for (char &ch : s) {
    index = dp[index][ch - 'a'];
    if (index == -1) {
        return false;
    }
}
return true;
Enter fullscreen mode Exit fullscreen mode

这里为什么要记录呢?因为查找字符是否出现在字符串中有很多方法,暴力遍历、位运算都是值得记录的。

Top comments (0)