描述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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → true分析这是一道很有挑战的题
''匹配任何单个字符。“*”匹配前一个元素的零个或多个
代码
1 public class RegularExpressionMatching { 2 3 public static void main(String[] args) { 4 // TODO Auto-generated method stub 5 System.out.println(isMatch("aa","a*")); 6 } 7 public static boolean isMatch(String s, String p) { 8 if (p.length() == 0) 9 return s.length() == 0; 10 11 // length == 1 is the case that is easy to forget. 12 // as p is subtracted 2 each time, so if original 13 // p is odd, then finally it will face the length 1 14 if (p.length() == 1) 15 return (s.length() == 1) && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'); 16 17 // next char is not '*': must match current character 18 if (p.charAt(1) != '*') { 19 if (s.length() == 0) 20 return false; 21 else 22 return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1)); 23 } else { 24 // next char is * 25 while (s.length() > 0 && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')) { 26 if (isMatch(s, p.substring(2))) 27 return true; 28 s = s.substring(1); 29 } 30 return isMatch(s, p.substring(2)); 31 } 32 } 33 34 }
转载于:https://www.cnblogs.com/ncznx/p/9180591.html
相关资源：数据结构—成绩单生成器