[DLdigest-11] 每日一道算法

2017 年 11 月 16 日 深度学习每日摘要 DLdigest

这道题是实现字符串的正则表达式匹配，这里只用实现’.’和’*‘的匹配即可。其中，’.’表示任意单一字符，’*’表示0个或多个前一字符。

可以使用动态规划算法来解决这个问题，假设字符串s的长度为m，字符串p的长度为n，可以使用一个状态矩阵state[m+1][n+1]来存储字符串s和字符串p的对应元素的匹配状态，若匹配，则为True，否则，为False。如元素state[i][j]表示字符串s的前i个元素与字符串p的前j个元素是否匹配。

首先，考虑一个特殊状态state[0][0]=True，因为两个空白字符串肯定是匹配的；

对于state[i][0]呢？即p为空白字符串时，无论s是什么，都不匹配，故state[i][0]=False（不包括i=0的情况）；

对于其他情况，只用遍历s和p即可，对于任意state[i][j]而言，可以根据p[j-1]的取值为’*’，’.’，以及其他字符来进行讨论：

对于p[j-1]为’*’，可以分为几种情况进行讨论：

对于像s="ab"并且p="abc*"这种情况，只要state[i][j-2]=True即可保证state[i][j]为True，因为p的最后两个元素不影响匹配的结果；

对于像s=”abb”并且p=”ab*“这种情况，如果state[i-1][j]=False，那么state[i][j]一定为False，同时，也应该确保s[i-1]=p[j-2]，即避免出现”abc”匹配成”ab*”的情况；

对于像s=”abb”并且p=”a.*”这种情况，因为’.’可以匹配任意单一字符，因此state[i-1][j]唯一决定着state[i][j]的取值；

对于p[j-1]=’.’的时候，例如像s=”ab”并且p=”a.”，state[i][j]只由state[i-1][j-1]来决定；

对于p[j-1]为其他字符的时候，例如像s=”abb”并且p=”a*b”，这个时候不仅需要state[i-1][j-1]为True，而且s[i-1]必须与p[j-1]相等才能得到state[i][j]=True；

将上面的情况综合整理之后，代码如下：

#include<iostream>
using namespace std;
class Solution {
public:    
    bool isMatch(string s, string p) {        
        int m=s.size(), n=p.size();        
        bool state[m+1][n+1];
        for(int i=0; i<=m; i++) {
            for(int j=0; j<=n; j++) {
                if(i==0 && j==0)
                    state[i][j]=true;                
                else if(i>0 && j==0)
                    state[i][j]=false;                
                else if(j>1 && p[j-1]=='*')
                    state[i][j]=state[i][j-2] || (i>0 && (s[i-1]==p[j-2] ||  p[j-2]=='.') && state[i-1][j]);
                else
                    state[i][j]=i>0 && state[i-1][j-1] && (p[j-1]=='.' || s[i-1]==p[j-1]);
           }
        }
        return state[m][n];
    }
};
        
int main()
{
    Solution s;
    cout<<boolalpha;
    cout<<s.isMatch("abb", ".b*")<<endl;
    cout<<s.isMatch("abb", "ab*")<<endl;
    cout<<s.isMatch("abb", "ab.")<<endl;
    cout<<s.isMatch("abb", "a.b")<<endl;
    cout<<s.isMatch("abb", "ab")<<endl;
    cout<<s.isMatch("aa", "a")<<endl;
    cout<<s.isMatch("aaa", "aaaa")<<endl;
    return 0;
}

程序运行结果：
true
true
true
true
false
false
false

每日一道算法——Container With Most Water
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

近期将以NLP领域论文分享及注意力机制的代码实践为主，每天一道算法会保持更新。欢迎大家留言分享深度学习知识或交流每日一道算法的思路，本期算法的解决方法将在下一期中讲解。

题图：Mona Lisa Sketch Hidden Alien

你可能会感兴趣的文章有：

[DLdigest-3] Python中让你无法预测的“是”