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
题解:又见递归的解法。这道题交了好多次,主要是细节要想清楚。总结一下要注意的地方:
if(p.length() == 1){ if(p.charAt(0) == ‘.‘ && s.length() == 1) return true; return s.equals(p); }
代码如下:
1 public class Solution { 2 public boolean isMatch(String s, String p) { 3 if(p.length() == 0) 4 return s.length() == 0; 5 6 if(s.length() == 0){ 7 if(p.length() == 1) 8 return false; 9 if(p.charAt(1) == ‘*‘) 10 return isMatch(s, p.substring(2)); 11 return false; 12 } 13 14 15 if(p.length() == 1){ 16 if(p.charAt(0) == ‘.‘ && s.length() == 1) 17 return true; 18 return s.equals(p); 19 } 20 21 if(p.length() >= 2 && p.charAt(1) != ‘*‘){ 22 //if p(1) is not *, we need p(0) equals to s(0) or p(0) equals ‘.‘ 23 if(p.charAt(0) == s.charAt(0) || p.charAt(0) == ‘.‘ && s.length() != 0) 24 //check if the left is also match 25 return isMatch(s.substring(1), p.substring(1)); 26 return false; 27 } 28 else{ 29 //if p(1) is ‘*‘,we check how many we can match from this * by trying 30 int i = 0; 31 char now = p.charAt(0); 32 while(i<s.length() && (s.charAt(i) == now || now == ‘.‘)){ 33 if(isMatch(s.substring(i+1),p.substring(2))) 34 return true; 35 i++; 36 } 37 //this means we don‘t use this ‘*‘ to match any character, just skip it 38 return isMatch(s, p.substring(2)); 39 } 40 } 41 }
【leetcode刷题笔记】Regular Expression Matching,布布扣,bubuko.com
【leetcode刷题笔记】Regular Expression Matching
原文:http://www.cnblogs.com/sunshineatnoon/p/3869055.html