Day 8

剑指offer 19.正则表达式匹配

题目描述

思路

动态规划：重点是找递推式

回顾动态规划的步骤：

1. dp数组以及下标的含义
2. 构造递推公式
3. dp数组的初始化
4. 遍历顺序
5. 打印dp数组

解答

class Solution {
    public boolean isMatch(String s, String p) {   
        int m=s.length();
        int n=p.length(); 
        //为了让i索引处的值就是第i个值，在前面加一个空字符
        s=' '+s;
        p=' '+p;
        char [] s1=s.toCharArray();
        char [] p1=p.toCharArray();
        boolean [][] f=new boolean[m+1][n+1];
        //初始化 
        f[0][0]=true;
        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                //如果 p1[j]!='*'
                if(p1[j]!='*'){
                    f[i][j]=i>0 && j>0 && f[i-1][j-1] && (s1[i]==p1[j] || p1[j]=='.');
                 // 如果 p1[j]=='*'
                }else{
                    f[i][j]=(j>1 && f[i][j-2]) || (i>0 && j>0 && f[i-1][j] && (s1[i]==p1[j-1] || p1[j-1]=='.'));
                }
            }
        }
        return f[m][n];
    }
}