10. Regular Expression Matching
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) { return isMatch(s, 0, p, 0); } private boolean isMatch(String s, int si, String p, int pi) { if(pi == p.length()) return si == s.length(); char pCurrent = p.charAt(pi); if(pi+1<p.length() && p.charAt(pi+1) == ‘*‘) //if followed by star { if(isMatch(s, si, p, pi+2)) //skip the first star part. return true; if(si<s.length() && (s.charAt(si) == pCurrent || pCurrent == ‘.‘) && isMatch(s, si+1, p, pi)) return true; return false; } else //match single character { if(si == s.length()) return false; //if s is already at the end. if(pCurrent != s.charAt(si) && pCurrent != ‘.‘) return false; //cannot find the match in s. return isMatch(s, si+1, p, pi+1); } } }
10. Regular Expression Matching && 44. Wildcard Matching
原文：http://www.cnblogs.com/neweracoding/p/5617728.html