剑指offer:52.正则表达式匹配

思路1 递归匹配

当模式中的第二个字符不是“*”时：
1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。

而当模式中的第二个字符是“”时：
可以有3种匹配方式：
1、模式后移2字符，相当于x被忽略；匹配0位
2、字符串后移1字符，模式后移2字符，x相当于只匹配一个字符；
3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为可以匹配多位；（包括匹配一位）

  1. 如果pattern[j] == '.'
  2. 如果str[i] == pattern[j]

以上两种情况都是i后移一位，然后j后移一位。

而当模式中的第二个字符是“*”时：

  1. 如果pattern[i] == '.' || str[i] == pattern[j],那么证明第一位相匹配，需要匹配0或多位 matchStr(str, i, pattern, j + 2) || matchStr(str, i + 1, pattern, j);；
  2. 反之，j后移两位。

代码

public class Solution {
    public boolean matchStr(char[] str, int i, char[] pattern, int j) {
            if (i == str.length && j == pattern.length) { // 字符串和模式串都为空
                return true;
            } else if (j == pattern.length) { // 模式串为空
                return false;
            }

        boolean next = (j + 1 < pattern.length && pattern[j + 1] == '*');// 模式串下一个字符是'*'


        //当模式中的第二个字符是“*”时：
            if (next) {
                if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) { 
                //匹配零位 & 匹配多位 （即使这一位相同或者是.，也有可能只匹配零位，匹配一位的情况包含在递归里了）
                    return matchStr(str, i, pattern, j + 2) || matchStr(str, i + 1, pattern, j);
                } else {
                    //匹配零位（当这一位不相同而且还不是.的时候，只能忽略了）
                    return matchStr(str, i, pattern, j + 2);
                }
            } 


        //当模式中的第二个字符不是“*”时：
        else {

                //匹配一位
                if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) {
                    return matchStr(str, i + 1, pattern, j + 1);
                } else {
                    //匹配这一位失败
                    return false;
                }
            }
    }

    public boolean match(char[] str, char[] pattern) {
        return matchStr(str, 0, pattern, 0);
    }
}

思路2 动态规划

动态规划转移方程：

boolean dp[i][j]表示str的前i个和pattern的前j个能否匹配

第一个字符为str[0]

从pattern角度看过去

第j个字符，当前字符pattern[j-1]不是“*”：

如果 pattern[j-1] == '.' || str[i-1] == pattern[j-1])，dp[i][j] = dp[i-1][j-1]

否则，dp[i][j] =false;

第j个字符，当前字符pattern[j-1]是“*”：

比较pattern中前一字符pattern[j-2]与str[i-1]是否匹配

如果 pattern[j-2] == '.' || str[i-1] == pattern[j-2])，那么分两种情况

  • 如果重复0次，dp[i][j] = dp[i][j-2]

  • 如果重复1次或者多次，dp[i][j] = dp[i-1][j]

否则，

  • 只有重复0次，dp[i][j] = dp[i][j-2]

动态规划初始条件：

str为空且pattern为空，为真: dp[0][0] = true

str不为空且pattern为空,为假: dp[1..sn][0] = false

pattern[j-1]=='*'时,dp[0,j]=dp[0,j-2];
否则dp[0,j]=false;

public class Solution {
    public boolean judge(char p,char s){
        if(p=='.')return true;
        else return p==s;
    }
    public boolean match(char[] str, char[] pattern)
    {
        int pn=pattern.length;
        int sn=str.length;
        boolean[][] dp=new boolean[sn+1][pn+1];
        //初始化
        dp[0][0]=true;
        for(int j=1;j<=pn;j++){
            if(pattern[j-1]=='*')dp[0][j]=dp[0][j-2];
        }
        for(int i=1;i<=sn;i++){
            for(int j=1;j<=pn;j++){
                boolean now = (pattern[j-1] == '*');// 模式串当前字符是'*'
                if(!now){
                    if(judge(pattern[j-1],str[i-1]))
                        dp[i][j]=dp[i-1][j-1];
                }
                else{
                    if(judge(pattern[j-2],str[i-1]))
                        dp[i][j]=dp[i][j-2]|dp[i-1][j];
                    else dp[i][j]=dp[i][j-2];
                }
            }
        }
        return dp[sn][pn];
    }
}

思路3 和原正则表达式一致，使用库函数匹配

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        return String.valueOf(str).matches(String.valueOf(pattern));
    }
}
import java.util.regex.*;
public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        String pat = String.valueOf(pattern);
        //把.替换为正则表达式的\w 用以匹配一个任意字符
        pat = pat.replaceAll("\\.", "\\\\w");
        Pattern pattern1 = Pattern.compile(pat);
        Matcher matcher = pattern1.matcher(String.valueOf(str));
        return matcher.matches();
    }
}

车轮滚滚 时间

import java.util.regex.*;

[]  ： 字符集合
()  ： 分组
?   ： 重复 0 ~ 1 次
+   ： 重复 1 ~ n 次
*   ： 重复 0 ~ n 次
.   ： 任意字符
\\. ： 转义后的 .
\\d ： 数字

{n} ：必须匹配n次
{n,}：必须匹配n次或以上
{n,m}：匹配次数在n到m之间，包括边界