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
1 public class Solution { 2 public boolean isMatch(String s, String p) { 3 if (s.equals(p)) { 4 return true; 5 } 6 7 int lenS=s.length(); 8 int lenP=p.length(); 9 if (lenP==0) { 10 return lenS==0; 11 } 12 if (lenP==1) { 13 if (p.equals(s)||(p.equals(".")&&lenS==1)) { 14 return true; 15 }else { 16 return false; 17 } 18 } 19 20 if (p.charAt(1)!=‘*‘) { 21 if (lenS>0 22 &&(s.charAt(0)==p.charAt(0)||p.charAt(0)==‘.‘)) { 23 return isMatch(s.substring(1), p.substring(1)); 24 } 25 return false; 26 }else { 27 while (s.length()>0&& 28 (s.charAt(0)==p.charAt(0)||p.charAt(0)==‘.‘)) { 29 if (isMatch(s, p.substring(2))) { 30 return true; 31 } 32 s=s.substring(1); 33 } 34 return isMatch(s, p.substring(2)); 35 } 36 } 37 }
leetcode Regular Expression Matching
原文：http://www.cnblogs.com/birdhack/p/4185685.html