当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

LeetCode[动态规划] - #10 Regular Expression Matching

发表于: 2015-07-21   作者:Cwind   来源:转载   浏览:
摘要: 原题链接:#10 Regular Expression Matching   要求: 实现正则表达式匹配,支持'.'和'*'。   '.'匹配任意单字符。 '*'匹配任何0个或多个之前元素。   匹配应当覆盖整个输入字符串,而不仅仅是子串。   函数原型: boolean isMatch(String /* string to chec

原题链接:#10 Regular Expression Matching

 

要求:

实现正则表达式匹配,支持'.'和'*'。

 

'.'匹配任意单字符。

'*'匹配任何0个或多个之前元素。

 

匹配应当覆盖整个输入字符串,而不仅仅是子串。

 

函数原型:

boolean isMatch(String /* string to check */ s, String /* patterns */ p)

 

例:

isMatch("aa", "a") → false

isMatch("aa", "aa") → true

isMatch("aaa", "aa") → false 

isMatch("aa", ".*") → true

isMatch("ab", ".*") → true

isMatch("aab", "c*a*b") → true

 

难度:困难

 

分析:

仅仅是原题中给出的六个示例的话,考虑采用贪心算法,从patterns字符串的尾部向前扫,对于patterns中的每个字符,在待检测字符串中扫到其所能匹配的最长子串,扫描完毕后判断是否到达待检测字符串的头部即可。使用贪心算法实现的该函数见此。但是该函数在应对如isMatch("aaaa", "ab*a*c*a")时会遇到问题,当扫描a*时便会到达待检字符串头部,产生错误结果,因此贪心算法并不适用。

 

仍然从待检字符串尾部向前扫描,设0≤j<s.length(),考虑对于子串s[j..s.length()-1]能够在正则表达式p找到匹配(match[j])的条件为s[j+1...s.length()-1]匹配且s[j]也能够在pattern中找到匹配。如何判断“s[j]也能够在pattern中找到匹配”呢?需要分两种情况讨论,设i为pattern索引,第一种情况:若p[i]不为'*',则进行单字符判断,当p[i]=='.'或p[i]==s[j]时match[j]成立;第二种情况:p[i]为"*",则match[j]成立的条件为p[i-1]=='.'或p[i-1]==p[j]。另外,在这种情况下若match[j]已经被置为true,就算p[i-1]=='.'||p[i-1]==p[j]不成立也应将其值保持,因为*出现时,其之前元素可以为0个。

 

解决方案:

Java - 340 ms

    

// Dynamic Programming Solution
    public boolean isMatch(String /* string to check */ s, String /* patterns */ p) {
        boolean[] match = new boolean[s.length()+1];
        for(int i=0; i<match.length; i++){
            match[i] = false;
        }
        match[s.length()] = true;
        for(int i=p.length()-1; i>=0; i--){
            if(p.charAt(i)=='*'){
                for(int j=s.length()-1; j>=0; j--){
                    match[j] = match[j]||match[j+1]&&(p.charAt(i-1)=='.'||p.charAt(i-1)==s.charAt(j));
                }
                i--;
            }else {
                for(int j=0; j<s.length(); j++){
                    match[j] = match[j+1]&&(p.charAt(i)=='.'||p.charAt(i)==s.charAt(j));
                }
                match[s.length()] = false;
            }
        }
        return match[0];
    }

 简单测试程序

LeetCode[动态规划] - #10 Regular Expression Matching

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号