Our blog, keeping you up-to-date on our latest news.

 

[LeetCode] Regular Expression Matching, Solution

January 17, 2015 at 10:10 pm | Algorithms | No comment

 

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).
 
The function prototype should be:
bool isMatch(const char *s, const char *p)
 
Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true

[Thoughts]

String match, and it is a typical DP problem.

create a two dimension table dp[s.length()+1][p.length()+1]

so dp[i][j] means whether string [0, i-1] matches pattern [0, j-1]
and dp[i+1][j+1] means whether string [0, i] matches pattern [0, j]

to initialize, dp[0][0] should be true, which means empty string matches empty string.
and dp[i][0] should be always false, when string is not empty, but the pattern is empty.
and dp[0][j] depends on whether there are ‘*’, because * could match empty string, for example ‘a*’ could match an empty string

to get the value dp[i+1][j+1]:
1. the simplest way, if s[i]==p[j]|| p[j]==’.’, that means we need to check whether s[0, i-1] matches p[0, j-1]
dp[i+1][j+1] = dp[i][j]

2. the complicated way, if(p[j]==’*’), that means we need to check the wildcard
the wildcard may take effective from 0 time to many times
if the wild card plays 0 time, then it matches an empty string with the previous character.
in this scenario, dp[i+1][j+1] = dp[i+1][j-1]

if the wild card plays once, then dp[i+1][j+1] = dp[i][j-1] && (s[i]==p[j-1] || p[j-1] == ‘.’)

if the wild card plays many times, the dp[i+1][j+1] = dp[i][j+1] && (s[i]==p[j-1] || p[j-1] == ‘.’)

3. the other scenarios, the default value “false” will be populated for the rest.

[Solution]

public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        //it actually is not necessary, as the default value is false for primitive boolean
        for(int i =0; i<s.length(); i++){
            dp[i+1][0] = false;
        }
        for(int j =0; j<p.length(); j++){
            if(j-1>=0 && p.charAt(j) == '*')
                dp[0][j+1]=dp[0][j-1];   
            else    
                //it actually is not necessary, as the default value is false for primitive boolean
                dp[0][j+1] = false;
        }
        for(int i =0; i<s.length(); i++){
            for(int j = 0; j< p.length(); j++){
                if(p.charAt(j) == s.charAt(i)||p.charAt(j) == '.'){
                    dp[i+1][j+1] = dp[i][j];   
                }
                else if(p.charAt(j) == '*' && j-1>=0){
                    if(p.charAt(j-1)==s.charAt(i) || p.charAt(j-1) == '.' )
                        // dp[i][j+1] means the * matches many times
                        // dp[i][j-1] means the * matches once
                        dp[i+1][j+1] = dp[i][j+1] || dp[i][j-1];
                    //the * matches 0
                    dp[i+1][j+1] = dp[i+1][j+1]||dp[i+1][j-1];;
                }
 
            }
        }
 
        return dp[s.length()][p.length()];
 
    }
}

<< Back to Blog Discuss this post

 
Comments are closed.