本文共 2162 字，大约阅读时间需要 7 分钟。
正则匹配
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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("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 character12 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 char18 }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
truetruefalsefalseabcdefg转载地址：http://fvtyo.baihongyu.com/