>

自由软件精神——“自由、开放、分享”。自由软件自诞生之日起,就秉承了学术自由的思想,信奉科学无国界,知识应该全人类共享。

ubuntu精神——人道待人,天下共享连接人人的信念。具有 ubuntu 精神的人心胸开阔,乐于助人,见贤思齐而不忌妒贤能......

leetcode刷题 Regular Expression Matching

 

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

 

 

根据P的下一个字符是否是'*'分情况讨论:

  1. 如果p的下一个字符不是'*',只需判断当前字符p[cur]和s[cur]是否相等,或者p[cur]='.',递归处理s[1:]和p[1:];
  2. 如果是p的下一个'*',则当s[cur]和p[cur]相等或者p[cur]='.'情况下,判断s[0~length:]任何一个是否和p[2:]match;


public class Solution {
    public boolean isMatch(String s, String p) {
        if (p.length() == 0) {
            return s.length() == 0;
        }

        // length == 1 is the case that is easy to forget.
        // as p is subtracted 2 each time, so if original
        // p is odd, then finally it will face the length 1
        if (p.length() == 1) {
            return (s.length() == 1)
                    && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');
        }

        // next char is not '*': must match current character
        if (p.charAt(1) != '*') {
            if (s.length() < 1) {
                return false;
            } else {
                return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')
                        && isMatch(s.substring(1), p.substring(1));
            }
        }else{// next char is *
            while (s.length() > 0
                   && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')) {
                if (isMatch(s, p.substring(2))) {
                    return true;
                }
                s = s.substring(1);
            }
            return isMatch(s, p.substring(2));
        }
    }
}

 

 

 

Meta

发布: 十二月 1, 2014

作者: Bone Lee 李智华

评论:  

字数统计: 424

下一篇: leetcode刷题 Minimum Window Substring

上一篇: leetcode刷题 Palindrome Partitioning II

Bookmark and Share

Tags

code leetcode python

comments powered by Disqus

返回顶部