Last active
March 24, 2017 01:12
-
-
Save wayetan/9401009 to your computer and use it in GitHub Desktop.
Regular Expression
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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 | |
*/ | |
public class Solution { | |
public boolean isMatch(String s, String p) { | |
if (p.length() == 0) | |
return s.length() == 0; | |
if (p.length() == 1 || p.charAt(1) != '*') { | |
if(s.length() < 1 || (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0))) | |
return false; | |
return isMatch(s.substring(1), p.substring(1)); | |
} else { | |
int i = -1; | |
while (i < s.length() && (i < 0 || p.charAt(0) == '.' || p.charAt(0) == s.charAt(i))) { | |
if (isMatch(s.substring(i + 1), p.substring(2))) | |
return true; | |
i++; | |
} | |
return false; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Solution { | |
public boolean isMatch(String s, String p) { | |
// Condition 1: if(p.charAt(j) == s.charAt(i)) --> dp[i][j] = d[i - 1][j - 1]; | |
// Condition 2: if(p.charAt(j) == '.') --> dp[i][j] = d[i - 1][j - 1]; | |
// Condition 3: if(p.charAt(j) == '*') --> two sub conditions: | |
// 1). if(p.charAt(j - 1) != s.charAt(i)) --> dp[i][j] = dp[i][j - 2] //in this case, a* only counts as empty | |
// 2). if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.' --> | |
// dp[i][j] = dp[i-1][j] //in this case, a* counts as multiple a | |
// or dp[i][j] = dp[i][j-1] // in this case, a* counts as single a | |
// or dp[i][j] = dp[i][j-2] // in this case, a* counts as empty | |
if (s == null || p == null) { | |
return false; | |
} | |
boolean[][] dp = new boolean[s.length()+1][p.length()+1]; | |
dp[0][0] = true; | |
for (int i = 0; i < p.length(); i++) { | |
if (p.charAt(i) == '*' && dp[0][i-1]) { | |
dp[0][i+1] = true; | |
} | |
} | |
for (int i = 0 ; i < s.length(); i++) { | |
for (int j = 0; j < p.length(); j++) { | |
if (p.charAt(j) == '.') { | |
dp[i+1][j+1] = dp[i][j]; | |
} | |
if (p.charAt(j) == s.charAt(i)) { | |
dp[i+1][j+1] = dp[i][j]; | |
} | |
if (p.charAt(j) == '*') { | |
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') { | |
dp[i+1][j+1] = dp[i+1][j-1]; | |
} else { | |
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]); | |
} | |
} | |
} | |
} | |
return dp[s.length()][p.length()]; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment