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). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab", "c*a*b") → trueA:
这道题目的思路的关键就是: 优先通过消去 * 来匹配。
-----------------第五遍-----------犯了个错误,就是:刚开始不是按照第二个位置是否是 ‘*’ 来分的,而先按照第一个位置是否匹配来做,比较SB-------------
public class Solution { public boolean isMatch(String s, String p) { if(s.length()==0) return p.length()==0 || (p.length()>=2 && p.charAt(1)=='*' && isMatch("",p.substring(2))); if(p.length()==0)// s is already not zero return false; if( p.length() > 1 && p.charAt(1)=='*') // first case, we do not match at this position return isMatch(s,p.substring(2)) || ( (s.charAt(0) == p.charAt(0) || p.charAt(0)=='.') && isMatch(s.substring(1),p)); else return (s.charAt(0) == p.charAt(0) || p.charAt(0)=='.') && isMatch(s.substring(1),p.substring(1)); } }
-----------第四遍------一遍过,不错不错---------嗯,出了2个typo-----
public class Solution { public boolean isMatch(String s, String p) { if(p.length() == 0) return s.length() ==0; if(s.length()==0 ) // now p is not empty return p.length() != 1 && p.charAt(1) == '*' && isMatch("",p.substring(2)); // if p.length() == 1 if(p.length() ==1) return s.length()==1 && (p.equals(s) || p.equals(".")); // now p is at least at length 2 if(p.charAt(1) != '*'){ // first char match return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') &&isMatch(s.substring(1),p.substring(1)); }else{// we have * at p(1) if(isMatch(s,p.substring(2)))// zero match at this position return true; return (s.charAt(0) == p.charAt(0) || p.charAt(0) =='.') && isMatch(s.substring(1),p); } } }
--------------第一遍-----------
下面这个方法,太慢,但很好地阐述了思想。--------不对,下面的算法, 当输入是:
String s = "aaaaaaaaaaaaab";
String p = "a*a*a*a*a*a*a*a*a*a*c";
的时候,几乎陷入死进去了。 ╮(╯▽╰)╭
public class Solution { public boolean isMatch(String s, String p) { assert (p != null && (p.length() == 0 || p.charAt(0) != '*')); return isMatch(s + "a", 0, p + "a", 0); } private boolean isMatch(String s, int startS, String p, int startP) { for (int i = startS; i < s.length() - 1; i++) {// NOT check last char if (startP >= p.length() - 1) {// we reach the end of pattern p return false; } char chS = s.charAt(i);// will not be '.' or '*' char chP = p.charAt(startP); char chPnext = p.charAt(startP + 1); if (chPnext == '*') { if (chS == chP || chP == '.') { if (isMatch(s, startS, p, startP + 2)) {// no match needed return true; } } else {// skip this chP and '*', and retest chS i--; startP = startP + 2; } } else { // chPnext != '*' if (chS == chP || chP == '.') { startP++; // pattern p , also move backward } else { return false; } } } return true; } }-------------------------------------------------------
上面有bug, 会总是停在 startS= 0 , 而 startP = 18, 20 里跳来跳去。
-------------------下面这个代码,硬是比我们的快一倍----关键是正确, !!!!!---哎~~~~~~~~
public class Solution { public boolean isMatch(String s, String p) { assert(p!=null && (p.length()==0 || p.charAt(0)!='*')); if(p.length()==0) return s.length()==0; if(p.length()==1 || p.charAt(1)!='*'){ if(s.length()<1 || (p.charAt(0)!='.' && p.charAt(0)!=s.charAt(0))) return false; return isMatch(s.substring(1),p.substring(1)); }else{ int i=-1; while(i<s.length() && (i<0 || p.charAt(0)=='.' || p.charAt(0)==s.charAt(i))){ if(isMatch(s.substring(i+1),p.substring(2))) return true; i++; } return false; } } }
--------------------------上面痛苦地跟狗一样,下面是最新的思想,来自于另一个wild string matching 的苦逼思考---------------利用了split的思想-------
但是, 最终的结果,还是不能处理下面这个 输入
// idea: // pattern like a* , NOT wildmatch, move to the last match position
// This would fail at "aaa", "ab*a*c*a"
while (beginIndex< s.length() && s.charAt(beginIndex) == curChar) {
beginIndex++;
}
这里,存在的问题,就是,move to the last matching position 是不行的。 因为,下一个c*可能是不需要match的。 (move to the last matching position) 只能对nextNode.isFollowedByStar == false的情况才有用。
哎,只能用递归的方法解决了。 到底没能用线性的方法解决这个问题。
算了,不管了,归根道理, 还是得用人家的方法解决。 何苦那么费劲巴力得去String.split()呢??
---------------------------------------------------第二遍,-----------用的是上面的substring的方式。------------要注意的问题是
1: 遇见 *的时候, 要对于是 的相等 的位置的下一个取substring。 否则~~~
2: 同上, 相应的 i 的位置,要 初始值为 -1
3: 对于 s=="” 的情况,不能简单地对应为: p = "a*"的情况, 应该归并到.*的循环里, 因为有可能是 a*a*的情况, 也是match 的。
--------------------------第三遍------------------------ 用了list来表示。 但是, 痛苦的地方,在于,不能很直观地loop, 否则的话,就会保存不了很多copy。
哎, 悲哀阿!~~~~~~悲哀的地方,见下边~~~~~~
最后,又折腾了2,3个小时,不得不返回原来的用string的方法。 最终折腾的代码如下:
思路和上面的一样。
public class Solution { public boolean isMatch(String s, String p) { if (p.length() == 0) { return s.length() == 0; } if (s.length() == 0) { // all the list are followed by star if (p.length() % 2 == 1) // if not all .*.* form return false; for (int i = 1; i < p.length(); i += 2) { if (p.charAt(i) != '*') return false; } return true; } if (p.length() == 1 || p.charAt(1) != '*') { if (p.charAt(0) == '.' || p.charAt(0) == s.charAt(0)) { return isMatch(s.substring(1), p.substring(1)); } else return false; } else {// current list is followed by star if (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0)) { return isMatch(s, p.substring(2)); } else {// find match at this position int curMatchPos = -1; do { curMatchPos++; boolean isMatchHere = isMatch(s.substring(curMatchPos), p.substring(2)); if (isMatchHere == true) return true; if (curMatchPos >= s.length()) return false; } while (p.charAt(0) == '.' || p.charAt(0) == s.charAt(curMatchPos)); return false; } } } }
主要复杂在后面跟着*的时候。
方法首先检查p 是否为空。 然后,检查 s 是否为空。
都不为空的话。
case 1: 如果p的长度==1 或者后面没有跟着*
直接对比当前的char , 看是否match
case 2: 如果当前的 p.charAt(0) , 后面跟着 * .
关键思想: 把所有的case,从递归调用,换成循环。 ,因此是在循环里, 逐个匹配p.charAt(0)。 如果当前位置匹配, 则递归调用,是否丐情况是否匹配。
这里,关键是用了一个循环,逐个匹配。
最后,所有的都没有匹配的时候, 则返回false;.
Mistakes:
1: 这个, 就是看别人的代码吧。 哎,你个SB, ,花了一晚上的时间, ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;两年,阿金费耶夫范德萨了(#‵′)凸o(╯□╰)oo(╯□╰)oT^TT^T?_?╭∩╮(︶︿︶)╭∩╮鄙视你!╭(╯^╰)╮⊙﹏⊙b汗-_-|||?_?O(∩_∩)O~(*^◎^*)o(>﹏<)o不要啊+_+-_-#~~~^_^~~~ :)O(∩_∩)O哈哈~↖(^ω^)↗(¯﹃¯)口水我靠( ‵o′)凸~\(≧▽≦)/~啦啦啦(⊙_⊙)?( ⊙ o ⊙ )啊!(*^__^*) 嘻嘻……(⊙_⊙)(⊙v⊙)嗯
Learned:
0: 以前不知道,后来被人指出,说写文章时不能用can't ,用can not不对是个语法错误
,要用cannot。
1: 对数组取substring, 的速度,并不比用 string index慢。 所以, 以后,如果可能,还是取substring吧。~~~~~~~~~~
2; 对一个string,用 * 来分割的话, 星号前要加两个 反斜杠
String[] pArray = p.split("\\*");
同理,对于用 dot 来分割: String extensionRemoved = filename.split("\\.")[0];
---------------------------第三遍的悲哀----------------
import java.util.*;
public class Solution {
public boolean isMatch(String s, String p) {
if( s.length() == 0 && p.length() ==0){
return true;
}
ArrayList<RNode> list = new ArrayList<RNode>();
//build list
for(int i =0;i< p.length();i++){
char ch = p.charAt(i);
if(i +1 <p.length() && p.charAt(i+1) == '*'){
RNode node = new RNode(ch,true);
list.add(node);
i++;
}else{
RNode node = new RNode(ch,false);
list.add(node);
}
}
// delete repeated node, like .* .* .* or a* a* a*
for(int i =0;i<list.size()-1;i++){
if(list.get(i).isStar && list.get(i+1).isStar && list.get(i).ch == list.get(i+1).ch){
list.remove(i+1);
i--;
}
}
return isMatch(s, list);
}
public boolean isMatch(String s, ArrayList<RNode> list){
if(list.isEmpty() ){
return s.length() == 0;
}
if(s.length() ==0){ // all the list are followed by star
for(int i =0;i< list.size();i++){
if(list.get(i).isStar==false)
return false;
}
return true;
}
if( list.get(0).isStar == false){
if(list.get(0).ch =='.' || list.get(0).ch == s.charAt(0)){
list.remove(0);
return isMatch(s.substring(1),list);
}else
return false;
}else{// current list is followed by star
if( list.get(0).ch !='.' && list.get(0).ch != s.charAt(0)){ //if not match, skip this node
list.remove(0);
return isMatch(s,list);
}else{// find match at this position
// choice 1: match here, and continue with current node
char ch = list.get(0).ch;
int chCount =0;
list.remove(0);
do{
boolean curResult = isMatch(s.substring(chCount), list);
if(curResult == true)
return true;
chCount++;
if(chCount>=s.length())
return list.isEmpty();
}while(ch =='.' || ch == s.charAt(chCount));
// after trying all possible positions of node 0 in list, we test the rest
return isMatch(s.substring(chCount), list);
}
}
}
}
class RNode{
boolean isStar;
char ch;
public RNode(char ch1, boolean isFollowedByStar){
ch = ch1;
isStar = isFollowedByStar;
}
}
上边list的地方,会被递归调用,导致list被更改。(因此,还需要加一个deep copy list 的函数) 哎, 悲哀阿悲哀
还是用string吧, 每次直接substring就行了
No comments:
Post a Comment