Leetcode: 10. Regular Expression Matching

Leetcode : Regular Expression Matching

对此leetcode上这么些题目,作者用了广大岁月来消食。
主题材料概略如下:


实现五个字符串s,t的相称,个中t字符串中的
‘.’ 能相称任何二个字符.
‘*’ 能充当0个或然多少个前面七个字符.
同盟结果要遮蔽整个字符串

多少个例子:
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

比如最后那一个事例c*a*b 能够和aab相配 就认证第八个* 充当了0个c,第二个
*出任了八个a。


该题有二种比较普遍的解法:递归和动规。以下小编就二种办法进行简易的深入分析。

Description

Implement regular expression matching with support for ‘.’ and ‘*’.

递归法

该题的叁个困难便是当t字符串中冒出了标识“ *
”时该怎么管理,不时候一下子并不可见清楚的把代码给写出来。大家能够直观地想,出现“
* ”时,该“ *
”能够充当0个,1个,2个…前边的字符,充当的长河还索要知足条件
(s[i]==p[0]) 或者(p[i]==’.’ && s[i]!=’’)。
大家将各种大概都与s串进行叁遍比较,若有一种能够匹配成功,便是相称成功。

若t字符串中的当前十分符号不是标记“ * ”就好办多了,大家直接对
s[i]==p[0] 或者 p[0]==’.’
举办判别,若相配成功,那么就能够展开下一步相配。

参照代码如下:(参照他事他说加以考察别人)

//递归方法
bool isMatch(string s, string p) 
{
        if ( p.empty() ) return s.empty();
        // p[1]不是*
        if ( p[1]!='*' )
        {
            return ( s[0]==p[0] || (p[0]=='.' && !s.empty()) ) && isMatch(s.substr(1), p.substr(1));
        }
        // p[1]是*
        int i = 0;
        for ( ; s[i]==p[0] || (p[0]=='.' && i

Example

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

动态规划法

若是对动态规划较为熟悉的人可能对于该方法可能更顺手些。

我们提供一个二维空间集合f[i][j] 其表示字符串s[0..i-1]能否和t[0…j-1]匹配成功,我们很快可以得到动态规划转移方程

当t[j-1]!=’*’时 f[i][j] = f[i-1][j-1] && ( s[i-1] == t[j-1] )

这个很好理解,s[i-1]和t[j-1]若相同,那么其s[0…i-2] 至 t[0…j-2]仍然能匹配成功时,那么这两段字符串就是匹配成功。

当t[j-1]==’*’时 t[j-1]可以充当0个或者多个t[j-2],只要满足以下两个条件中任何一个,f[i][j] 结果即为true t[j-1]充当0个t[j-2] : f[i][j] = f[i][j-2] t[j-1]充当1个及以上t[j-2] :f[i][j] = (s[i - 1] == p[j - 2] || ‘.’ == p[j - 2]) && f[i - 1][j]

上述动规方程中的 f[i - 1][j] 包含了 t[j-1]充当2个,3个…多个t[j-2] 的所有可能性,并且动规过程中,我们已经计算并保存了结果。

参考代码如下:(参考别人)

bool isMatch(string s, string p) {

 int m = s.size(), n = p.size();
        vector> f(m + 1, vector(n + 1, false));

        f[0][0] = true;//空串与空串匹配成功
        for (int i = 1; i <= m; i++)//s串与空串匹配结果为false
            f[i][0] = false;
        // p[0..j - 1] 能与空串匹配 需满足 p[j - 1]=='*' 并且 p[0..j - 3] 能与空串匹配
        for (int j = 1; j <= n; j++)
            f[0][j] = j > 1 && '*' == p[j - 1] && f[0][j - 2];

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (p[j - 1] != '*')
                    f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || '.' == p[j - 1]);
                else
                    f[i][j] = f[i][j - 2] || (s[i - 1] == p[j - 2] || '.' == p[j - 2]) && f[i - 1][j];

        return f[m][n];
}

两种方法不同的思想,其中有相通的部分,都能解决问题,记录一下以便以后回顾。

 

http://www.bkjia.com/cjjc/1029064.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1029064.htmlTechArticleLeetcode : Regular Expression Matching
对于leetcode上这些标题,作者用了相当的多时光来消化吸取。 标题大要如下:
完成四个字符串s,t的相配,在那之中t字符串中…

思路

  • 匹配难点
  • ‘.’ 相配任性单个字符,’*’ 匹配前边的字符0次或频仍
  • 因为急需思虑后面包车型大巴字符,所以从后往前相称。
  • 考虑 ‘‘时的超过常规规景况,假设 ‘
    ‘前边的字符和要同盟的千篇一律,则分两张情状,即相配0次或频仍
  • 假若不等同,则要同盟的不改变,然后跳到*字符前边的先头。
  • 并未有说理解,看代码吧

代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int slen = s.size();
        int plen = p.size();

        return matchFunc(s, slen - 1, p, plen - 1);
    }

    bool matchFunc(string& s, int i, string &p, int j){
        if(i < 0 && j < 0) return true;
        if(i < 0 ) return p[j] == '*' ? matchFunc(s, i, p, j - 2) : false;
        if(j < 0) return false;

        if(s[i] == p[j] || p[j] == '.'){
            return matchFunc(s, i - 1, p, j - 1);
        }
        else if(p[j] == '*'){ 
            bool res = false;
            //特殊情况
            if(j - 1 >= 0){
                if(p[j - 1] == '.' || p[j - 1] == s[i])
                    res =  matchFunc(s, i - 1, p, j) || matchFunc(s, i - 1, p, j - 2);
            }

            return res || matchFunc(s, i, p, j - 2);
        }

        return false;
    }
};

动态规划

  • 再切磋区里面还见到了一种动态规划的算法。在这边也作二个介绍,不得不感慨一句,大佬仍旧多啊。
  • dp[i][j]
    表示s[0..i)和p[0..j)的相配结果,若为ture,则相称,不然不匹配
  • 则合计有以下处境:
    • dp[i][j] = dp[i – 1][j – 1],if p[j – 1] != ‘*’ &&
      (s[i – 1] == p[j – 1] || p[j – 1] ==
      ‘.’),注意下标的决定,dp[i][j]的下标是长度,而p[j-1]对应于dp[i][j]
    • dp[i][j] = dp[i][j – 2], if p[j – 1] == ‘*’,
      且匹配0次
    • dp[i][j] = dp[i – 1][j] && (s[i – 1] == p[j – 2] ||
      p[j – 2] == ‘.’),此时p[j – 1] == ‘*’ 且至少相配壹次
  • 代码如下:

    class Solution {
    public:
        bool isMatch(string s, string p) {
            int slen = s.size();
            int plen = p.size();
    
            vector<vector<bool>> dp(slen + 1, vector<bool>(plen + 1, false));
            dp[0][0] = true;
            for(int i = 0; i <= slen; ++i){
                for(int j = 1; j <= plen; ++j){
                    if(p[j - 1] == '*'){
                        dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
                    }
                    else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
            }
    
            return dp[slen][plen];
        }
    };
    

总结

  • 递归往往能够立异的
  • 向大佬学习!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图