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 boolean isMatch(String s, String p) { //p 为空 if(p.isEmpty()) return s.isEmpty(); //p 当前匹配的字符后面不接* if(p.length() == 1 || p.charAt(1) != ‘*‘) { //如果第一个字符匹配则各往后走一个字符，否则不匹配 if(isFirstMatch(s, p)) return isMatch(s.substring(1), p.substring(1)); else return false; } //p 当前匹配的字符后接* //当第一个字符匹配的时候，先判断把当前p匹配的X*去掉（因为可以为0个X）的情况，如aaa匹配a*a //然后再将s往后走一个字符继续判断 while(isFirstMatch(s, p)) { if(isMatch(s, p.substring(2))) return true; s = s.substring(1); } //当s的第一个字符不匹配时跳过X*继续匹配 return isMatch(s, p.substring(2)); }
思路二：动态规划思想。
public boolean isMatchII(String s, String p) { boolean[] match = new boolean[s.length()+1]; Arrays.fill(match, false); //match[j]代表s[j~sLen-1]与p[i~pLen-1]匹配 match[s.length()] = true; for(int i=p.length()-1;i>=0;i--){ if(p.charAt(i)==‘*‘){ for(int j=s.length()-1;j>=0;j--) match[j] = match[j]||match[j+1]&&(p.charAt(i-1)==‘.‘||s.charAt(j)==p.charAt(i-1)); i--; } else{ for(int j=0;j<s.length();j++) match[j] = match[j+1]&&(p.charAt(i)==‘.‘||p.charAt(i)==s.charAt(j)); //TODO：这句代码不清楚为什么 match[s.length()] = false; } } return match[0]; }
原文：http://www.cnblogs.com/ivanyangzhi/p/4734540.html