AcWing 30. 正则表达式匹配--Java代码
原题链接
困难
作者:
木木灬
,
2019-05-10 16:20:27
,
所有人可见
,
阅读 1656
算法1
(递归)
- 递归结束条件,如果两个字符串都到了最后,返回true
- 如果其中一个结束,则匹配不成功,返回false
- 如果当前两个位置的值相同或p的值为’.’,则递归下一位置
- 如果下一位置为‘*’,当前位置两个字符创相同或者p的字符串为‘.’,则分类讨论,因为‘※’可以代表0,1,多次,所以可以s不动,p向后移动两位;或者s向后一位;或者同时移动,s一位,p两位
- 如果前面的都没成功,则匹配失败,返回false;
Java 代码
class Solution {
public boolean isMatch(String s, String p) {
if(s==null||p==null)
return false;
if((s.length()!=0&&p.length()==0))
return false;
char[] str = s.toCharArray();
char[] pat = p.toCharArray();
return matchCore(str,0,pat,0);
}
private boolean matchCore(char[] str, int indexOfStr, char[] pattern, int indexOfPattern) {
if (indexOfStr == str.length && indexOfPattern == pattern.length){
return true;}
if (indexOfStr < str.length && indexOfPattern == pattern.length)
return false;
if (indexOfPattern + 1 < pattern.length && pattern[indexOfPattern + 1] == '*') {
if ((indexOfStr < str.length && pattern[indexOfPattern] == '.')
|| (indexOfStr < str.length && pattern[indexOfPattern] == str[indexOfStr])) {
return matchCore(str, indexOfStr, pattern, indexOfPattern + 2)
|| matchCore(str, indexOfStr + 1, pattern, indexOfPattern)
|| matchCore(str, indexOfStr + 1, pattern, indexOfPattern + 2);
} else {
return matchCore(str, indexOfStr, pattern, indexOfPattern + 2);
}
}
if (indexOfStr < str.length && (pattern[indexOfPattern] == str[indexOfStr] || (pattern[indexOfPattern] == '.'))){
return matchCore(str, indexOfStr + 1, pattern, indexOfPattern + 1);
}
return false;
}
}