Leetcode Regular Expression Matching求教

'.' 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

不是很清楚是怎样matchLeetcode的原题在上面，其中最后一个是isMatch("aab", "c*a*b") → true，代表的就是有n个c，n个a和一个b的字符串。题目认为这两个是match的。但是网上看到的解法，全部都是只要s和p首字母不match而且p的首字母不是*的时候便return false。并且这样写的code也通过了所有的test case。所以想问一下，是不是原题最后一个example写错了啊？

‘*’ 是指可以匹配前面的字符出现 0次或多次的。这个例子“c*”匹配0个'c'~ 后面“a*”匹配前面的“aa”  ~所以return true

通过所有test case的code
public boolean isMatch(String s, String p) {
        // base case
        if (p.length() == 0) {
                return s.length() == 0;
        }

        // special case
        if (p.length() == 1) {

                // if the length of s is 0, return false
                if (s.length() < 1) {
                        return false;
                }

                //if the first does not match, return false
                else if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) {
                        return false;
                }

                // otherwise, compare the rest of the string of s and p.
                else {
                        return isMatch(s.substring(1), p.substring(1));
                }
        }

        // case 1: when the second char of p is not '*'
        if (p.charAt(1) != '*') {
                if (s.length() < 1) {
                        return false;
                }
                if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) {
                        return false;
                } else {
                        return isMatch(s.substring(1), p.substring(1));
                }
        }

        // case 2: when the second char of p is '*', complex case.
        else {
                //case 2.1: a char & '*' can stand for 0 element
                if (isMatch(s, p.substring(2))) {
                        return true;
                }

                //case 2.2: a char & '*' can stand for 1 or more preceding element,
                //so try every sub string
                int i = 0;
                while (i<s.length() && (s.charAt(i)==p.charAt(0) || p.charAt(0)=='.')){
                        if (isMatch(s.substring(i + 1), p.substring(2))) {
                                return true;
                        }
                        i++;
                }
                return false;
        }
}

Ziyan 发表于 2015-6-4 05:12
‘*’ 是指可以匹配前面的字符出现 0次或多次的。这个例子“c*”匹配0个'c'~ 后面“a*”匹配前面的“aa”  ...

太谢谢拉~