题目链接
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
|
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
思路
难点在于 ‘*’ 字符可以匹配0-n个前面的元素。
我们先简化问题。不考虑 ‘*’ 字符的话。只需要按顺序匹配是否完全一致，或者p[i]==’.’即可。
接着考虑’‘ 由于 号 匹配0-n个前面的元素。重点在于0个。
所以我们需要根据 下一个patten字符 是不是 ‘*’ 来处理情况。
不是*则需要保证 p.charAt(pos2) == '.' || s.charAt(pos1) == p.charAt(pos2) 负责匹配不成功。
是* 则匹配 0- n 此后，进行pos的移动，继续往下匹配。
代码
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
return match(0, 0, s, p);
}
public boolean match(int pos1, int pos2, String s, String p) {
if (pos2 >= p.length()) {
//patten使用完毕
return pos1 >= s.length();
}
if (pos2 + 1 < p.length() && p.charAt(pos2 + 1) == '*') {
//下一位是* 当前不一定需要匹配上
for (; pos1 < s.length(); pos1++) {
if (s.charAt(pos1) == p.charAt(pos2) || p.charAt(pos2) == '.') {
if (match(pos1, pos2 + 2, s, p)) {
return true;
}
} else {
//当前位没匹配上
break;
}
}
//*号匹配零个字符
return match(pos1, pos2 + 2, s, p);
} else if (pos1 < s.length()) {
//下一位非* 当前需要匹配上
if (p.charAt(pos2) == '.' || s.charAt(pos1) == p.charAt(pos2)) {
//当前位置匹配上 匹配下一个位置
return match(pos1 + 1, pos2 + 1, s, p);
}
return false;
}
return false;
}
|
