内容简介：但是有一个比较明显的优化点，重复计算了很多状态，可以用一个二维数组保存状态
Given an input string (s) and a pattern (p), implement regular
expression matching with support for '.' and '*'.
'.' Matches any single character. '*' Matches zero or more of the
preceding element. 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 *. Example 1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match
the entire string "aa". Example 2:
Input: s = "aa" p = "a " Output: true Explanation: ' ' means zero or
more of the precedeng element, 'a'. Therefore, by repeating 'a' once,
it becomes "aa". Example 3:
Input: s = "ab" p = ". " Output: true Explanation: ". " means "zero or
more (*) of any character (.)". Example 4:
Input: s = "aab" p = "c a b" Output: true Explanation: c can be
repeated 0 times, a can be repeated 1 time. Therefore it matches
"aab". Example 5:
Input: s = "mississippi" p = "mis is p*." Output: false
比较难的一道题
第一思路是双指针解决，两个指针分别匹配中移动，如果最后都指向队尾，则匹配成功，利用贪心的思想，尽可能的往后匹配，最后判断两个串是否还有剩余，但没有考虑到一个情况，可能出现匹配多的情况，下面的情况就cover不了。
1111
1*1111
无法通过贪心解决的时候，就可以在无法决定的地方进行分支判断，按照正向的就是递归的思想，不要忘了保存状态。
正向可以通过递归方式解决
public boolean isMatch(String s, String p) {
if(s.length()==0 && p.length()==0) return true;
if(p.length()>=2 && p.charAt(1)=='*'){
if(p.length()>=1 && s.length()>=1 && (p.charAt(0)==s.charAt(0) || p.charAt(0)=='.')){
if(isMatch(s.substring(1),p)) return true;
}
if(isMatch(s,p.substring(2))) return true;
}
if(p.length()>=1 && s.length()>=1 && (p.charAt(0)==s.charAt(0) || p.charAt(0)=='.')){
if(isMatch(s.substring(1),p.substring(1))) return true;
}
return false;
}
但是有一个比较明显的优化点，重复计算了很多状态，可以用一个二维数组保存状态
int[][] dp;
public boolean isMatch(String s, String p) {
dp=new int[s.length()+1][p.length()+1];
dp[0][0]=1;
return ref(s,p);
}
public boolean ref(String s, String p) {
if(dp[s.length()][p.length()]!=0) return dp[s.length()][p.length()]==1;
boolean first=p.length()>=1 && s.length()>=1 && (p.charAt(0)=='.' || p.charAt(0)==s.charAt(0));
if(p.length()>=2 && p.charAt(1)=='*'){
if(first){
if(ref(s.substring(1),p)){
dp[s.length()][p.length()]=1;
return true;
}
}
if(ref(s,p.substring(2))){
dp[s.length()][p.length()]=1;
return true;
}
}
if(first){
if(ref(s.substring(1),p.substring(1))){
dp[s.length()][p.length()]=1;
return true;
}
}
dp[s.length()][p.length()]=-1;
return false;
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Writing Apache Modules with Perl and C
Lincoln Stein、Doug MacEachern / O'Reilly Media, Inc. / 1999-03 / USD 39.95
Apache is the most popular Web server on the Internet because it is free, reliable, and extensible. The availability of the source code and the modular design of Apache makes it possible to extend Web......一起来看看 《Writing Apache Modules with Perl and C》 这本书的介绍吧!
