Wednesday, October 9, 2013

Regular Expression Matching !!!!!!!!!!!!!!!!!!!!

Q:
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") → true
A:
这道题目的思路的关键就是:  优先通过消去 * 来匹配。   

-----------------第五遍-----------犯了个错误,就是:刚开始不是按照第二个位置是否是 ‘*’ 来分的,而先按照第一个位置是否匹配来做,比较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