跳到主要内容

字符串匹配

通配符匹配​

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

示例1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例2:

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

方案 动态规划​

思路: 在给定的模式p中，只会有三种类型的字符出现:

  • 小写字母a-z，可以匹配对应的一个小写字母；
  • 问号?，可以匹配任意一个小写字母；
  • 星号∗，可以匹配任意字符串，可以为空，也就是匹配零或任意多个小写字母。

其中，小写字母和问号的匹配是确定的，而*号的匹配是不确定的，因此我们需要枚举所有的匹配情况。为了减少重复枚举，我们可以使用动态规划来解决本题。

  1. 状态定义: dp[i][j]表示字符串s的前i个字符和模式p的前j个字符是否能匹配。

  2. 状态转移方程:

    • 如果p[j]==s[i]时，方程为:dp[i][j]=dp[i-1][j-1]
    • 如果p[j]为?时，那么对s[i]没有任何要求，方程为:dp[i][j]=dp[i-1][j-1]
    • 如果p[j]为*号时，同样对s[i]没有任何要求，但是*号可以匹配0或任意多个小写字母，因此方程为:dp[i][j]=dp[i][j-1]||dp[i-1][j]

  3. 初始化状态:

    • dp 初始都为 false
    • dp[0][0]=true，即当字符串s和模式p均为空时，匹配成功
    • dp[i][0]=false,即空模式无法匹配非空字符串
    • dp[0][j] 时:
      • 如果 p[j-1]=='*' ，则有 dp[0][j]=true;

  4. 问题答案: dp[row][col] 为最终答案

:::details 点击查看代码

function isMatch(s, p) {
    const row=s.length;
    const col=p.length;
    const dp=new Array(row+1).fill(0).map(()=>new Array(col+1).fill(false));
    dp[0][0]=true;
    for(let i=1;i<=col;i++){
        if(p[i-1]=='*'){
            dp[0][i]=true;
        }else{
            break;
        }
    }
    for(let i=1;i<=row;i++){
        for(let j=1;j<=col;j++){
            if(p[j-1]=='*'){
                dp[i][j]=dp[i][j-1]||dp[i-1][j];
            }else if(p[j-1]=='?'||s[i-1]==p[j-1]){
                dp[i][j]=dp[i-1][j-1];
            }
        }
    }
    return dp[row][col];
};

:::

性能分析:

  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)

字符串匹配​

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

示例1:

输入：haystack = "hello", needle = "ll"
输出：2

示例2:

输入：haystack = "aaaaa", needle = "bba"
输出：-1

示例3:

输入：haystack = "", needle = ""
输出：0

方案A 通过暴力匹配​

思路:

我们可以让字符串 needle 与字符串 haystack 的所有长度为 m 的子串均匹配一次。

为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 -1。

:::details 点击查看代码

function strStr(haystack,needle){
    const hLen=haystack.length;
    let nLen=needle.length;
    if(!nLen){
        return 0
    }
    for(let i=0;i+nLen<=hLen;i++){
        let flag=true;
        for(let j=0;j<nLen;j++){
            if(haystack[i+j]!=needle[j]){
            flag=false;
            break;
            }
        }
        if(flag){
            return i
    }
    }
    return -1
}
// const haystack='aabaabaaf';
// const needle='aabaaf'
// const haystack='a';
// const needle='a'
const haystack='';
const needle="";
console.log(strStr(haystack,needle));

:::

性能分析:

  • 时间复杂度：O(n×m)，其中 n 是字符串 haystack 的长度，m 是字符串 needle 的长度。最坏情况下我们需要将字符串 needle 与字符串 haystack 的所有长度为 m 的子串均匹配一次。

  • 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

方案B 通过 KMP 算法​

思路:

  • 通过 needle 创建前缀表 next 数组
  • 定义变量
    • i 记录访问的 haystack 字符
    • j 记录访问的 needle 字符
  • 如果 haystack[i]==needle[j] 时: j++
  • 如果 haystack[i]!=needle[j] 时: j 要取 j 前一个字符所对应的前缀表值 即 next[j-1]
  • 如果 j==needle.length 时，说明已经遍历完 needle ，i-needle.length+1 即为所求的索引值

:::details 点击查看代码

function getNext(needle){
    let len=needle.length;
    let j=0;
    let next=[j];
    for(let i=1;i<len;i++){
        while(j>0&&needle[i]!=needle[j]){
            j=next[j-1];
        }
        if(needle[i]==needle[j]){
            j++
        }
        next[i]=j;
    }
    return next;
}
function subStr(haystack,needle){
    let hLen=haystack.length;
    let nLen=needle.length;
    if(!nLen){
        return 0
    }
    let j=0;
    let next=getNext(needle);
    for(let i=0;i<hLen;i++){
        while(j>0&&haystack[i]!=needle[j]){
            j=next[j-1];
        }
        if(haystack[i]==needle[j]){
            j++
        }
        if(j==nLen){
            return i-nLen+1
        }
    }
    return -1
}

// const haystack = "hello"
// const needle = "ll"
const haystack = "a"
const needle = "a"
console.log(subStr(haystack,needle));

:::

正则表达式匹配​

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

示例1:

输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例2:

输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

方案 动态规划​

思路: 题目中的匹配是一个逐步匹配的过程:我们每次从字符串p中取出一个字符或者字符+*的组合，并在s中进行匹配。对于p中一个字符而言，它只能在s中匹配一个字符，匹配的方法具有唯一性；而对于p中字符+*的组合而言，它可以在s中匹配任意自然数个字符，并不具有唯一性。因此我们可以考虑动态规划，对匹配的方案进行枚举。

  1. 状态定义: dp[i][j]表示s的前i个字符与p中的前j个字符是否能够匹配。
  2. 状态转移方程:
    • 若s[i]==p[j],则有方程:dp[i][j]=dp[i-1][j-1]
    • 若p[j]="*":
      • 如果s[i]==p[j-1],则有方程:dp[i][j]=dp[i-1][j]||dp[i][j-2]
      • 如果s[i]!=p[j-1],则有方程:dp[i][j]=dp[i][j-2]
    • 若p[j]=".",那么p[j]一定可以成功匹配s中的任意一个小写字母，则有方程:dp[i][j]=dp[i-1][j-1]
  3. 初始化状态:
    • dp 初始为 false
    • dp[0][0]=true ,即两个空字符串是可以匹配的
  4. 问题答案: dp[row][col] 为最终答案

:::details 点击查看代码

function match(s,p,i,j){
    if(i==0){
        return false;
    }
    if(p[j-1]=='.'){
        return true;
    }
    return s[i-1]==p[j-1];
}
function isMatch(s, p) {
    const row=s.length;
    const col=p.length;
    const dp=new Array(row+1).fill(0).map(()=>new Array(col+1).fill(false))
    dp[0][0]=true;
    for(let i=0;i<=row;i++){
        for(let j=1;j<=col;j++){
            if(p[j-1]=='*'){
                dp[i][j]=dp[i][j-2];
                if(match(s,p,i,j-1)){
                    dp[i][j]=dp[i][j]||dp[i-1][j];
                }
            }else{
                if(match(s,p,i,j)){
                    dp[i][j]=dp[i-1][j-1];
                }
            }
        }
    }
    return dp[row][col];
};

:::

性能分析:

  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)