java - 如何优化我的回溯解决方案以匹配正则表达式?
问题描述
这是我试图在 LeetCode 上解决的一个问题:
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *
我已经为这个问题想出了一个回溯解决方案,就像这样,
class Solution {
public boolean isMatch(String s, String p) {
p = p.replaceAll("\\*+", "*");
return myIsMatch(s, p);
}
public boolean myIsMatch(String s, String p) {
if(s==null || p == null){
return false;
}
if(p.equals("*")){
return true;
}
int i = 0;
while(i<s.length() && i<p.length() && s.charAt(i)==(p.charAt(i))){
i++;
if(i<s.length() && i>=p.length()){
return false;
}
}
if(i == s.length() && i == p.length()){
return true;
}else if(i != s.length() && i == p.length()){
return false;
}else if(i == s.length() && i != p.length()){
if(p.charAt(i) == '*'){
return myIsMatch("", p.substring(i+1));
}else{
return false;
}
}
if(p.charAt(i)=='?'){
if(i+1<s.length() && i+1<p.length()){
return myIsMatch(s.substring(i+1), p.substring(i+1));
}else if(i+1<s.length() && i+1>=p.length()){
return false;
}else if(i+1>=s.length() && i+1<p.length()){
return myIsMatch(s.substring(i+1), p.substring(i+1));
}else{
return true;
}
}else if(p.charAt(i)=='*'){
for(int k = i;k<=s.length();k++){
if(myIsMatch(s.substring(k), p.substring(i+1))){
return true;
}
}
}else{
return false;
}
return false;
}
}
这适用于大多数测试用例,除了以下病态的测试用例,程序似乎没有退出,
s = "abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb"
p ="**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"
如何优化代码以处理此类输入?非常感谢任何帮助!
解决方案
我不认为该程序不会退出。您的问题具体是您的算法对于您提供的输入运行速度不够快,并且您的时间用完了。
回溯解决方案不是匹配正则表达式的最佳方法。我认为您当前的算法具有 O(N^2) 的时间复杂度,但它可能会好得多,也许使用动态编程解决方案。我建议你重新考虑你的方法。
实际上,现在我想最好的解决方案确实是 O(mn)。
编辑:问题在于,除了会导致 O(mn) 时间复杂度的回溯解决方案之外,您还要遍历辅助函数中的字符串,使其类似于 O(n^3)。与其直接修改输入字符串,不如尝试使用 memoization 来解决问题。
推荐阅读
- mysql - 导入一系列包含一个字段的 .CSV 文件,同时在其他字段中添加额外的“已知”数据
- zeromq - 在客户端使用 ZAP 处理程序的 ZeroMQ 曲线断言
- objective-c - FatSecret API“无效签名”
- html - 正常和初始(css)之间有什么区别
- arrays - 如何将 AD 计算机名称传递给数组?
- html - 如何使用 CSS flexbox 调整背景和前景层的大小
- ruby-on-rails - 如何调用回调?
- javascript - 有条件地将类分配给 PrimeNG p-datatable 行组标题
- r - R download.file 下载没有图像的原始 html
- dotnetbrowser - 如何在 DotNetBrowser 中创建 JSArray?