最近刷LeetCode遇到关于正则匹配的编程题，在这里记录下解题思路。
Regular Expression Matching
Link
Regular Expression Matching - LeetCode
Description
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
Recursive Solution
Discusss
当模式中的第二个字符不是“*”时：
- 如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
- 如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
而当模式中的第二个字符是“*”时：
- 如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
- 如果字符串第一个字符跟模式第一个字符匹配，可以有2种匹配方式：
- 模式后移2字符，相当于x*被忽略;
- 字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位;
Code
public class Solution {
public boolean isMatch(String s, String p) {
if (s.equals("") && p.equals("")) return true;
if (!s.equals("") && p.equals("")) return false;
if (p.length() > 1 && p.charAt(1) == '*') {
return isMatch(s, p.substring(2)) ||
(s.length() != 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0)) && isMatch(s.substring(1), p));
}
if (s.length() != 0 && p.length() != 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0)))
return isMatch(s.substring(1), p.substring(1));
return false;
}
}
Dynamic Planning Solution
Discusss
1. If p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1];
2. If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3. If p.charAt(j) == '*':
here are two sub conditions:
1 if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //in this case, a* only counts as empty
2 if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
dp[i][j] = dp[i-1][j] // in this case, a* counts as multiple a
or dp[i][j] = dp[i][j-2] // in this case, a* counts as empty
Code
public class Solution {
public boolean isMatch(String s, String p) {
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
for (int i = 0; i < p.length(); i++)
if (p.charAt(i) == '*' && dp[0][i-1]) dp[0][i+1] = true;
for (int i = 0 ; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.') dp[i+1][j+1] = dp[i][j];
if (p.charAt(j) == s.charAt(i)) dp[i+1][j+1] = dp[i][j];
if (p.charAt(j) == '*') {
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.')
dp[i+1][j+1] = dp[i+1][j-1];
else
dp[i+1][j+1] = (dp[i][j+1] || dp[i+1][j-1]);
}
}
}
return dp[s.length()][p.length()];
}
}
Wildcard Matching
Link
Description
Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
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", "*") ? true
isMatch("aa", "a*") ? true
isMatch("ab", "?*") ? true
isMatch("aab", "c*a*b") ? false
Recursive Solution
Discuss
当模式中的第一个字符不是“*”时：
- 如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
- 如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
而当模式中的第一个字符是“*”时：
- 模式后移1字符，相当于*被忽略;
- 字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位;
Code
@Deprecated
//(TimeLimitExceededException)
public class Solution {
public boolean isMatch(String s, String p) {
if (s.length() == 0 && p.length() == 0) return true;
if (s.length() != 0 && p.length() == 0) return false;
if (s.length() > 0 && (p.charAt(0) == '?' || s.charAt(0) == p.charAt(0))) return isMatch(s.substring(1), p.substring(1));
if (p.charAt(0) == '*') return isMatch(s, p.substring(1)) || (s.length() > 0 && isMatch(s.substring(1), p));
return false;
}
}
Dynamic Planning Solution
Discuss
1. If p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1];
2. If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3. If p.charAt(j) == '*':
here are two sub conditions:
dp[i][j] = dp[i-1][j] // in this case, * counts as multiple
or dp[i][j] = dp[i][j-1] // in this case, * counts as empty
Code
public class Solution {
public boolean isMatch(String s, String p) {
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int j = 0; j < p.length(); j++)
if (p.charAt(j) == '*' && dp[0][j]) dp[0][j+1] = true;
for (int i = 0; i < s.length(); i++)
for (int j = 0; j < p.length(); j++)
if (p.charAt(j) == '?' || s.charAt(i) == p.charAt(j)) dp[i+1][j+1] = dp[i][j];
else if (p.charAt(j) == '*') dp[i+1][j+1] = dp[i][j+1] || dp[i+1][j];
return dp[s.length()][p.length()];
}
}
