Regular Expression Matching
比较典型的动态规划题，重点就在于*号的匹配上。
分三步走：
- 当模式串为空时。检查内容串是否为空（为空则返回
true，反之返回false）。注意这里反过来是不成立的，也就是不能检查当内容穿为空时，模式串是否为空，因为如果模式串最后一个字符是*，那么即便此时模式串不为空，总结结果也有可能是true。
- 当模式串长度为1或者模式串的第二个字符不为
*时。这种情况比较简单，只要比较这个字符串的第一个字符即可，两个字符串的第一个字符相等或者模式串的第一个字符为.则返回true，反之就是false。
- 最后，就是要处理模式串第二个字符是
*的情况了，这种情况下，模式串的第一个字符可以匹配内容串中任意多个连续的相同字符（包括0个），那么就从『一个都匹配』到『匹配所有符合要求的字符』进行一遍循环，那么在循环中，问题就变为两个字符串的字串是否匹配的问题了，对函数进行递归调用即可，判断返回结果以决定是否返回true。最后如果循环结束之后仍没有返回，就证明无论如何匹配，*都无法合理匹配，那就证明两个字符串无法匹配，所以返回false。
实现代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Solution {
public boolean isMatch(String s, String p) {
if (p.length() == 0) return s.length() == 0;
if (p.length() == 1 || p.charAt(1) != '*') {
if (s.length() > 0 && (p.charAt(0) == s.charAt(0)
|| p.charAt(0) == '.')) {
return isMatch(s.substring(1, s.length()),
p.substring(1, p.length()));
} else {
return false;
}
} else {
int i = 0;
do {
if (isMatch(s.substring(i, s.length()), p.substring(2, p.length()))) {
return true;
}
i++;
} while (i <= s.length() && (p.charAt(0) == s.charAt(i - 1) || p.charAt(0) == '.'));
return false;
}
}
}
|
