题目描述
blablabla
样例
blablabla
递归的解法:
与一般字符串匹配不同的是,这题多了.和星号两个匹配符;对于.可以匹配任何字符,处理较为简单,但是对于星号处理较为复杂。
为了分类更加简洁,我们在比较str[a]与pattern[b]时,不先去比较这二者是否相等,而是去判断pattern[b+1]是否为星号,不为星号的话,直接比较str[a]和pattern[b],匹配时指针均右移,如果pattern[b+1]等于星号,那么我们分以下几种情况:
1.str[a] != pattern[b],意味着如果星号不表示把pattern[b]出现次数置为0,那么就不匹配,所以此时我们考虑下一种状态matchStr(str, pattern, m, n + 2)。
2.str[a] == pattern[b],此时就是不确定性有限状态机问题了,我们可以进一步转化为三种状态。
第一种:和1一样,即使当前字符匹配,我们还是让它出现的次数为0,说不定p后面的字符还会和s当前字符匹配呢,这种情况我们容易忽略,也就是matchStr(str, pattern, m, n + 2)。
第二种:星号使得pattern[b]出现一次,也就是b直接右移两位进行比较即可。即matchStr(s,p,a+1,b+2)。
第三种:星号使得pattern[b]出现不小于2次,那么可以递归的转化为子问题,b不变,a右移一位。matchStr(s,p,a+1,b)。
如何说上面分类比较难以想到的话,那么这题的边界情况同样需要小心翼翼,稍微出错便不能ac。
str与pattern都为空,匹配,但是str为空也可以匹配pattern不为空,比如pattern为2星号,星号可以让前面字符出现次数变为0。当然,一旦模式串pattern为空,而str非空,那么肯定是不匹配的。
从下面代码可以看见,边界情况用了两条语句,在b刚刚越界时判断一下a是否也越界了;另外,由于分类时首先考虑的是pattern[b+1],所以还需要判断b是否是最后一个字符,如果是,只有在a也到达最后的字符且匹配整体才匹配。
作者:昂昂累世士
链接:https://www.acwing.com/solution/acwing/content/1098/
java 代码
public boolean isMatch(String s, String p) {
if (p.length() == 0) return s.length() == 0;
char[] str = s.toCharArray();
char[] pattern = p.toCharArray();
return matchStr(str, pattern, 0, 0);
}
private boolean matchStr(char[] str, char[] pattern, int a, int b) {
// 有效性检验:str到尾,pattern到尾,匹配成功
if (a == str.length && b == pattern.length) {
return true;
}
// pattern 先到尾巴,匹配失败
if (a != str.length && b == pattern.length)
return false;
// 模式第2个不是*,且字符串第1个跟模式第1个匹配,则都后移1位,否则直接返回false
if ((a != str.length && pattern[b] == str[a])
|| (pattern[b] == '.' && a != str.length)) {
//判断第二个是否是*,当前如果n已经到pattern的末尾了还需要往前走一步
if ((b + 1 < pattern.length && pattern[b + 1] != '*')
|| b + 1 == pattern.length) {
return matchStr(str, pattern, a + 1, b + 1);
}
}
//如果是*
if (b + 1 < pattern.length && pattern[b + 1] == '*') {
//str[a] == pattern[b],此时就是不确定性有限状态机问题了,我们可以进一步转化为三种状态。
if (a < str.length && str[a] == pattern[b] || (pattern[b] == '.' && a != str.length)) {
if (matchStr(str, pattern, a, b + 2))
return true;
if (matchStr(str, pattern, a + 1, b + 2))
return true;
if (matchStr(str, pattern, a + 1, b))
return true;
} else {
//str[a] != pattern[b],意味着如果星号不表示把p[b]出现次数置为0,那么就不匹配
// 所以此时我们考虑下一种状态match(s,p,a,b+2)。
return matchStr(str, pattern, a, b + 2);
}
}
return false;
}