10. Regular Expression Matching (Hard)
https://leetcode.com/problems/regular-expression-matching/
Given an input string (s
) and a pattern (p
), 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).
Note:
s
could be empty and contains only lowercase lettersa-z
.p
could be empty and contains only lowercase lettersa-z
, and characters like.
or*
.
Example 1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa" p = "a*" Output: true Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab" p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input: s = "aab" p = "c*a*b" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:
Input: s = "mississippi" p = "mis*is*p*." Output: false
Solutions
class Solution {
// This problem is a little bit complicated, do not waste too much time and effort.
// The problem requires to match up the entire target string, rather than the partial match.
// The key point of resolve this problem is to handle every * respectively.
// When dealing with *, be careful that it must be used with preceding element,
// which means a single * without prefix is a wrong case.
// And be careful that * could mean 0 or >=1 preceding elements, both cases need to be
// treated differently,
public boolean isMatch(String s, String p) {
if (p.length() == 0) {
return s.length() == 0;
}
// when p.length == 1, consists of 3 situations
// from the perspective of recursion, this condition should be the exit of searching.
if (p.length() == 1) {
// Notice that p cannot be * since it needs prefix elements and the situation
// becomes simplified.
// s.length() must be 1, p could be . or other char.
// to match s, p's length must be 1, otherwise s cannot be covered by p
if (s.length() != 1) {
return false;
}
//if the first does not match, return false
if (p.charAt(0) != s.charAt(0) && p.charAt(0) != '.') {
return false;
}
// otherwise, compare the rest of the string of s and p.
return isMatch(s.substring(1), p.substring(1));
}
// when the second char of p is not '*'
if (p.charAt(1) != '*') {
if (s.length() < 1) {
return false;
}
// what if s="ss", p="*s" ? Strictly speaking, * is used to match preceding element,
// can not be situated at the head of string.
// And . can be used at the leftmost position since it matches any single character
if (p.charAt(0) != s.charAt(0) && p.charAt(0) != '.') {
return false;
} else {
// p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'
return isMatch(s.substring(1), p.substring(1));
}
}
// when the second char of p is '*'
// both the following two cases must be checked simultaneous and equally.
// check case 1 that * means 0 preceding element
if (isMatch(s, p.substring(2))) {
return true;
}
// check case 2 that * stands for 1 or more preceding element,
// so try all the possible substrings
int i = 0;
while (i < s.length() && (s.charAt(i) == p.charAt(0) || p.charAt(0) == '.')) {
if (isMatch(s.substring(i + 1), p.substring(2))) {
return true;
}
i++;
}
return false;
}
}
Reference
https://www.programcreek.com/2012/12/leetcode-regular-expression-matching-in-java/