regular expression mathinc --Java写竟然超时了／。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

regular expression mathinc --Java写竟然超时了／。

regular expression mathinc --Java写竟然超时了／。# JobHunting - 待字闺中

t*r2015-03-01 08:03

1 楼

regular expression mathinc --Java写竟然超时了／。
同样的算法c++没问题
谁能帮我看看那里怎么改进？
谢谢了！

t*r2015-03-01 08:03

2 楼

http://ideone.com/e.js/Q4cT4w

t*r2015-03-01 08:03

3 楼

public class T10 {
static boolean matchFirst(String s, String p){
System.out.println("in matchFirst: s is "+s+",p is: "+p+";");
System.out.println("s is empty "+ s.isEmpty());
System.out.println("p is empty "+ p.isEmpty());
if(s.isEmpty() ^ p.isEmpty()) return false;
if(s.isEmpty() && p.isEmpty()) return true;
return ( s.charAt(0)==p.charAt(0) || p.charAt(0)=='.' );
}
public static boolean isMatch(String s, String p) {
if (p.isEmpty() )return (s.isEmpty());

if(p.length()==1 || p.charAt(1)!='*') {
if(!matchFirst(s,p)) return false;
return isMatch(s.substring(1), p.substring(1));
} else {

if (isMatch(s, p.substring(2))) return true;
while(true){
if(isMatch(s, p.substring(2))) return true;
if(!matchFirst(s, p)) break;
s=s.substring(1);
}
}
return false;
}

public static void main(String[] args){
String s = "aaa";
String p = "ab*a";
boolean ret = isMatch(s, p);
System.out.println(ret);
}
}