LeetCode 10 - Regular Expression Matching

作者 QIFAN 日期 2017-02-15
LeetCode 10 - Regular Expression Matching

原题链接: 10. Regular Expression Matching


题干

匹配含 *. 的正则表达式。
. 表示任意字符
* 表示 0 个或多个上一个字符的重复

思路

让我想起了 LeetCode 291 - Word Pattern II

几个测试:
“” ““ false
“ ““ true
“” “**” true
“ ““ true
“a” “
“ false
“a“ “*“ false

从以上测试归纳:* 如果作为一个正则,一定与其前面的字符成对出现,不然 * 就是一个字符。
. 比较容易理解。

因为符号会影响之前的 pattern ,所以从后往前进行遍历。情况有:

  • pattern 没了,str 也没了,返回 true (base case 1)
  • str 还有, pattern 没了或 str 没了,pattern 只有一个长度,返回 false (base case 2)
  • 遇到 * ,查看上一个字符 char
    • 若上一个字符不是 ‘.’ ,str 位置往前直到不是 char
    • 若上一个字符是 . ,str 每往前一步,进行下一轮递归,如果结果为 true ,直接返回,如果为 false ,str 继续往前一个字符,再进行下一轮递归直到 s 长度为 0 ,返回 false
  • 遇到 . ,str 和 pattern 位置同时往前 1 位,进行下一轮递归。
  • 遇到其他字符,与 pattern 当前位置比较,不一样返回 false ,一样就 str 和 pattern 同时向前,继续递归。

再用一个 memo 数组存储已经计算过的 s 和 p 。

代码看上去很烦,懒得整理了。

代码:

public class Solution {
int[][] memo = null;
public boolean isMatch(String s, String p) {
int slength = s.length();
int plength = p.length();
if (memo == null) {
memo = new int[slength + 1][plength + 1];
}
// 若已经计算过,直接返回结果
if(memo[slength][plength] == 1) {
return false;
} else if (memo[slength][plength] == 2) {
return true;
}
// base case 1: 两边都完成遍历
if (slength == 0 && plength == 0) {
memo[slength][plength] = 2;
return true;
}
// base case 2
if ((slength > 0 && plength == 0) || (slength == 0 && plength < 2)) {
memo[slength][plength] = 1;
return false;
}
// 获取 pattern 的最后一个字符
char c = p.charAt(plength - 1);
// 如果是 * 且 pattern 长度大于等于 2
if (c == '*' && plength >= 2) {
char prec = p.charAt(plength - 2);
// 如果 * 的前一个 是 .
if (prec == '.') {
if (plength == 2) {
memo[slength][plength] = 2;
return true;
}
int si = slength;
// check 每次前进一步的结果
while (si > 0) {
if (isMatch(s.substring(0, si), p.substring(0, plength - 2))) {
memo[slength][plength] = 2;
return true;
}
si--;
}
// 此时 si 是 0
if (isMatch(s.substring(0, si), p.substring(0, plength - 2))) {
memo[slength][plength] = 2;
return true;
}
memo[slength][plength] = 1;
return false;
} else {
int si = slength - 1;
// 同理,如果上一个字符与 * 前的字符一样,都可以前进一步计算
while (si >= 0 && s.charAt(si) == prec) {
if (isMatch(s.substring(0, si + 1), p.substring(0, plength - 2))) {
memo[slength][plength] = 2;
return true;
}
si--;
}
// 此时 s = “”
if (isMatch(s.substring(0, si + 1), p.substring(0, plength - 2))) {
memo[slength][plength] = 2;
return true;
} else {
memo[slength][plength] = 1;
return false;
}
}
} else if (c == '.') {
if (slength == 0) {
memo[slength][plength] = 1;
return false;
}
if (isMatch(s.substring(0, slength - 1), p.substring(0, plength - 1))) {
memo[slength][plength] = 2;
return true;
} else {
memo[slength][plength] = 1;
return false;
}
// 其他字符
} else {
if (slength == 0) {
memo[slength][plength] = 1;
return false;
}
if (s.charAt(slength - 1) == c) {
if (isMatch(s.substring(0, slength - 1), p.substring(0, plength - 1))) {
memo[slength][plength] = 2;
return true;
} else {
memo[slength][plength] = 1;
return false;
}
}
memo[slength][plength] = 1;
return false;
}
}
}