LeetCode 44 - Wildcard Matching

作者 QIFAN 日期 2017-03-19
LeetCode 44 - Wildcard Matching

原题链接: 44. Wildcard Matching


题干

实现支持 ?* 的正则匹配。给定一对字符串,返回是否匹配。

'?' 代表匹配一个任意字符
'*' 代表匹配任意字符串,包括空字符串
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

思路

设有字符串 a 和 b ,index 分别为 i 和 j 。b[j] 分下列三种情况:

  • '*'
    • i 不变,j++ (匹配空字符串)
    • i++ ,j++ (匹配 a[i])
    • i++ ,j 不变 (匹配 a[i] 及后面一个)
  • '?' i++; j++
  • 其他字符。
    • a[i] == b[j]; i++; j++
    • return false

base case :

  • i ,j 都到达末尾 ,匹配成功 ,true
  • i ,j 只有其中一个到达末尾,匹配失败, false

减少重复计算,另设一个 memo[a.length][b.length]

时间复杂度为 $O(a.length() * b.length())$ ,空间复杂度为 $O(a.length() * b.length())$ 。

代码:

public boolean isMatch(String s, String p) {
int i = 0;
int j = 0;
int[][] memo = new int[s.length() + 1][p.length() + 1];
return isMatch(s, i, p, j, memo);
}
private boolean isMatch(String s, int sindex, String p, int pindex, int[][] memo) {
// 如果都到尽头,完全匹配
if (sindex >= s.length() && pindex >= p.length()) {
memo[sindex][pindex] = 1;
return true;
}
// 如果字符串到达尽头,而正则此时并不是 '*' ;或字符串没到尽头正则表达式到了,不匹配
if ((sindex >= s.length() && p.charAt(pindex) != '*') || (pindex >= p.length()) ) {
return false;
}
// 如果字符串到达尽头,正则表达式此时为 '*' ,返回正则向后一位的结果
if ((sindex >= s.length() && p.charAt(pindex) == '*')) {
return isMatch(s, sindex, p, pindex + 1, memo);
}
// 如果已经存了该位置的结果,直接返回
if (memo[sindex][pindex] != 0) {
return memo[sindex][pindex] > 0;
}
char c = p.charAt(pindex);
switch(c) {
case '?':
memo[sindex][pindex] = isMatch(s, sindex + 1, p, pindex + 1, memo) ? 1 : -1;
break;
case '*':
memo[sindex][pindex] = (isMatch(s, sindex, p, pindex + 1, memo) || isMatch(s, sindex + 1, p, pindex + 1, memo) || isMatch(s, sindex + 1, p, pindex, memo)) ? 1 : -1;
break;
default:
if (c == s.charAt(sindex)) {
memo[sindex][pindex] = isMatch(s, sindex + 1, p, pindex + 1, memo) ? 1 : -1;
} else {
memo[sindex][pindex] = -1;
}
break;
}
return memo[sindex][pindex] > 0;
}