LeetCode Top 100 Liked Questions 10.Regular Expression Matching (Java版; Hard)

​​welcome to my blog​​

LeetCode Top 100 Liked Questions 10.Regular Expression Matching (Java版; Hard)

题目描述

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

思路

• 按照p当前字符的下一个字符是否为’*'分成两大类进行讨论
• 注意’.'的存在
• base case: 只有当p和s都遍历完才能返回true
• p中有*的时候,可能会出现s判断完p没判断完的情况,如aa和a*; ab和.*c, 所以使用indexs的地方都要先确保indexs<s.length();
• 另外, 没有确保indexs<s.length();的地方不要用到indexs+1, 如Core(s, p, indexs+1, indexp+1);

暴力递归版

class Solution {
    public boolean isMatch(String s, String p) {
        return Core(s, p, 0, 0);
    }
    public boolean Core(String s, String p, int indexs, int indexp){
        //base case
        if(indexp==p.length() && indexs==s.length())
            return true;
        if(indexp==p.length() && indexs<s.length())
            return false;
        //
        boolean res = false;
        if(indexp+1<p.length() && p.charAt(indexp+1) == '*'){
            if(indexs<s.length() && (s.charAt(indexs)==p.charAt(indexp) || p.charAt(indexp)=='.'))
                res  = Core(s, p, indexs+1, indexp);
            res = res || Core(s, p, indexs, indexp+2);
        }
        else{//p没有下一个或者p的下一个不是*
            if(indexs<s.length() && (s.charAt(indexs)==p.charAt(indexp) || p.charAt(indexp)=='.'))
                res = Core(s, p, indexs+1, indexp+1);
            return res;
        }
        return res;
    }
}

动态规划版; 初始条件i=s.length(), j=p.length()-1; 根据暴力递归的思想改成动态规划版

class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[s.length()][p.length()] = true;
        boolean currMatch = false; //s[i]是否与p[j]匹配
        //i从s.length()开始表示的情况是: s判断完,p没有判断完
        for(int i=s.length(); i>=0; i--){
            for(int j=p.length()-1; j>=0; j--){
                currMatch = (i<s.length() && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.'));
                if(j+1<p.length() && p.charAt(j+1)=='*'){
                    //dp[i][j+2]对应两种可能, 一种是currMatch为true时,但是不匹配, 另一种是currMath为false时,只能不匹配
                    dp[i][j] = dp[i][j+2] || (currMatch && dp[i+1][j]);
                }
                else{//j+1>=p.length() || p.charAt(j+1)!='*'
                    dp[i][j] = currMatch && dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }
}