一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 351|回复: 3
收起左侧

[Leetcode] Leetcode Regular Expression Matching求教

[复制链接] |试试Instant~ |关注本帖
水莹莹 发表于 2015-6-4 04:19:20 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 水莹莹 于 2015-6-4 04:23 编辑

'.' 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写错了啊?

Ziyan 发表于 2015-6-4 05:12:40 | 显示全部楼层
‘*’ 是指可以匹配前面的字符出现 0次或多次的。这个例子“c*”匹配0个'c'~ 后面“a*”匹配前面的“aa”  ~所以return true
回复 支持 2 反对 0

使用道具 举报

 楼主| 水莹莹 发表于 2015-6-4 04:37:44 | 显示全部楼层
通过所有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;
        }
}
回复 支持 反对

使用道具 举报

 楼主| 水莹莹 发表于 2015-6-10 06:52:18 | 显示全部楼层
Ziyan 发表于 2015-6-4 05:12
‘*’ 是指可以匹配前面的字符出现 0次或多次的。这个例子“c*”匹配0个'c'~ 后面“a*”匹配前面的“aa”  ...

太谢谢拉~
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 09:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表