LeetCode 10 Regular Expression Matching
https://leetcode.com/problems/regular-expression-matching/
状态:dp[i][j] 是一个布尔数组,表示 string[i:] 和 pattern[j:] 能否匹配成功。
选择:对于 pattern 中的字母和 . 并没有选择可言;对于 *,我们可以选择匹配其之前的字母 0~N 次,放到递归中则是匹配或者不匹配。
- 匹配:则 pattern 保持不变,string 进一位。
- 不匹配,则 string 保持不变,pattern 进两位(因为 * 和其之前的字符为一个整体)。
注意:
- 为了代码的可读性,使用一个专门的布尔数组来记录 memory 中是否有之前计算过的值。
- 注意需要妥善处理边界情况。
代码:
class Solution {
String s, p;
boolean[][] data;
boolean[][] computed;
public boolean isMatch(String s, String p) {
this.s = s;
this.p = p;
data = new boolean[s.length()+1][p.length()+2];
computed = new boolean[s.length()+1][p.length()+2];
return dp(0, 0);
}
private boolean dp(int i, int j) {
// When pattern is over, return true if the string also is over.
if(j>=p.length()) return i>=s.length();
boolean current = false;
if(i<s.length()) {
if(computed[i][j]) return data[i][j];
current = (s.charAt(i) == p.charAt(j)) || (p.charAt(j) == '.');
}
// Notice the * pattern must act with its previous character.
if(p.length() > j+1 && p.charAt(j+1) == '*') data[i][j] = dp(i, j+2) || (current && dp(i+1, j));
else data[i][j] = current && dp(i+1, j+1);
computed[i][j] = true;
return data[i][j];
}
}
Links: LeetCode-474-Ones-and-Zeroes