正则匹配
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
1 package com.rust.TestString; 2 3 class Solution { 4 public boolean isMatch(String s, String p) { 5 if (p.length() == 0) { 6 return s.length() == 0; 7 } 8 if (p.length() == 1) { 9 return (s.length() == 1) && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'); 10 } 11 // next char is not '*': must match current character 12 if (p.charAt(1) != '*') { 13 if (s.length() == 0) { 14 return false; 15 } else { 16 return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') 17 && isMatch(s.substring(1), p.substring(1)); // judge next char 18 } 19 } else { // next char is '*' 20 while (s.length() > 0 && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')) { 21 if (isMatch(s, p.substring(2))) { 22 return true; 23 } 24 s = s.substring(1); 25 } 26 return isMatch(s, p.substring(2)); 27 } 28 } 29 } 30 31 32 public class RegularExpressionMatching { 33 public static void main(String args[]){ 34 Solution solution = new Solution(); 35 String s = "abcdefg"; 36 System.out.println(solution.isMatch(s, "abcde*")); 37 System.out.println(solution.isMatch(s, ".*")); 38 System.out.println(solution.isMatch("abcdefg", "a.*")); 39 System.out.println(solution.isMatch("abcdefg", ".b.")); 40 System.out.println(solution.isMatch("abcdefg", "")); 41 System.out.println(s); 42 } 43 }
输出：
false
true
true
false
false
abcdefg
