LeetCode 题解
    正则匹配系列

    正则匹配系列

    leetcode44 Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’

    ‘?’ Matches any single character. ‘*’ Matches any sequence of characters (including the empty sequence).

    bool isMatch(string s, string p) {
	// 除去重复的*
    string tmp="";
    bool first=true;
    for(auto c : p) {
        if (c=='*') {
            if (first) {
                first=false;
                tmp.push_back(c);
            }
        } else {
            tmp.push_back(c);
            first=true;
        }
    }

    p=tmp;

    vector<vector<bool> > dp(s.size()+1, vector<bool>(p.size()+1, false));
    if (p.size()>0 && p[0]=='*') dp[0][1]=true;
    dp[0][0]=true;

    for(int i=1;i<dp.size();++i) {
        for(int j=1;j<dp[0].size();++j) {
			// ? 或者字符相等，结果取决于前面的串
            if (p[j-1]=='?' || s[i-1]==p[j-1])
                dp[i][j]=dp[i-1][j-1];
			// 当前是 * ，可以消去一个或不消去
            else if (p[j-1]=='*')
                dp[i][j]=dp[i][j-1] || dp[i-1][j];
        }
    }
    return dp[s.size()][p.size()];
}

    leetcode10

    Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

    ‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element.

    bool isMatch(string s, string p) {
    string tmp="";
    bool first=true;
    for(auto c : p) {
        if (c=='*') {
            if (first) {
                first=false;
                tmp.push_back(c);
            }
        } else {
            tmp.push_back(c);
            first=true;
        }
    }

    p=tmp;

    vector<vector<bool> > dp(s.size()+1, vector<bool>(p.size()+1, false));
    dp[0][0]=true;
    if (p.size()>0 && p[0]=='*') dp[0][1]=true;
    for(int i=2;i<dp[0].size();++i)
        if(p[i-1]=='*') dp[0][i]=dp[0][i-2];

    for(int i=1;i<dp.size();++i) {
        for(int j=1;j<dp[0].size();++j) {
			// 字符相等或者模式是任意一个字符
            if((s[i-1]==p[j-1])||(p[j-1]=='.'))
				dp[i][j]=dp[i-1][j-1];
            else if (p[j-1]=='*') {
				// 看*号前的字符是否匹配
                if ((s[i-1]==p[j-2])||(p[j-2]=='.'))
					dp[i][j]=dp[i-1][j];
				// 若*号当做空串用前面需要匹配
                if (j>1 && !dp[i][j]) dp[i][j]=dp[i][j-2];
            }
        }
    }
    return dp[s.size()][p.size()];
}

    #DP

    矩阵旋转字符串翻转