Problem:
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
Analysis:
This question is really not hard if you use DFS way to match the string. (not dynamic programming!) The most challengeing part is to clearly differentiate different cases. Basic idea: (recursive) 1. iff p.charAt(1) = '*', it means we can use p.charAt(0) to match zero or more characters(susscive) in the s. Then continue to compare the remaining part. 2. iff p.charAt(1) != '*', it means we can don't need to care p.charAt(1), we can soly compare the p.charAt(0) and s.charAt(0). The key point is that if p.charAt(1) = '*', it can affect the match of p.charAt(0), thus we must treat it carefully. Like other matching problems, use s to match aginst p!!!! It is better for us to write the checking condition based on p. Detail: 1. base case (when p is "") <this is where a success match ends with> It means all p's characters have already been matched. Iff s is also "", it means p and s perfectly matched. Otherwise, we return false for this branch. ---------------------------------------------------------------------- if (p.length() == 0) return s.length() == 0; ---------------------------------------------------------------------- Note: this check is very common for following situations, p and s must perfectly match with each other. 2. when p has only one character. iff s is null, return false, iff s is not null, we check if s.charAt(0) == p.charAt(0) or p.charAt(0) = '.'. iff not we return false; iff yes, we continue to compare remaining part. ---------------------------------------------------------------------- if (p.length() == 1) { if (s.length() == 0) return false; else if (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0)) return false; else return isMatch(s.substring(1), p.substring(1)); } ---------------------------------------------------------------------- Note: you may notice that we do not have following logic: if (s.length () > 1) return false; This case would finally be hanlded at "return isMatch(s.substring(1), p.substring(1));". The reason why do not write in that way is to use the power of recursive and not to break it is code structure. 3. when p has more than one character. 3.1 p.charAt(1) != '*' Following the same checking in 2. Note: we don't bother the check p.charAt(1) = s.charAt(1) at this step. ---------------------------------------------------------------------- if (p.charAt(1) != '*') { if (s.length() < 1) return false; if (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0)) return false; else return isMatch(s.substring(1), p.substring(1)); } ---------------------------------------------------------------------- 3.2 p.charAt(1) == '*' 3.2.1 we use the case: '*' represent no pre character(this is the hardest case using other method) if (isMatch(s, p.substring(2))) return true; 3.2.2 '*' represent one (more) pre charcter (many times) int index = 0; while (index < s.length() && (s.charAt(index) == p.charAt(0) || p.charAt(0) == '.' )) { if (isMatch(s.substring(index+1), p.substring(2))) return true; index++; } return false; Note: '.' can represent as many characters as possible in s.
Solution:
public class Solution { public boolean isMatch(String s, String p) { if (p.length() == 0) return s.length() == 0; if (p.length() == 1) { if (s.length() == 0) return false; else if (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0)) return false; else return isMatch(s.substring(1), p.substring(1)); } //at least two characters left at p if (p.charAt(1) != '*') { if (s.length() < 1) return false; if (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0)) return false; else return isMatch(s.substring(1), p.substring(1)); } else{ if (isMatch(s, p.substring(2))) return true; int index = 0; while (index < s.length() && (s.charAt(index) == p.charAt(0) || p.charAt(0) == '.' )) { if (isMatch(s.substring(index+1), p.substring(2))) return true; index++; } return false; } } }