### [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()]; } } |