LeetCode 44. Wildcard Matching (动归)

小咪咪 2024-04-17 23:12 175阅读 0赞

题目：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1][]

说明在注释中

class Solution {
    public:
        bool isMatch(string s, string p) {
            /*
            //动态规划
            //想办法把转移方程写出来
            //先把所有可能情况全部列出来
            //d[0][0] = (p[0]=="?"||p[0]=="*"||p[0]==s[0]);
            //d[1][0] = (p[j]=="*"&&d[i-1][j]);
            //d[1][1] = (d[i-1][j-1] && (p[j]=="*"||p[j]=="?"||p[j]==s[i]))//前面的情况只要满足就不管他怎么满足，就顾着最后一个
            //d[0][1] = (p[j-1]=="*"&&(p[j]=="*"||p[j]=="*"||p[j]==s[i])&&d[i-1][j])
            //将最关键的几个列出来之后发现有些难整合，思考将d[1][0]和d[0][1]整合进d[1][1]，那么就需要d[0][-1]和d[-1][0]的出现
            //然后我们其实可以想到忽略了一种情况，s="", p="*",所以两个空串可以作为d[0][0]
            //演进方程
            //d[0][0] = true;
            //d[1][0] = false;
            //d[0][1] = (p[1] == "*") *可以匹配空 
            //i和j从1开始遍历，所以p对应的应该是p[j-1]
            //d[i][j] = (d[i-1][j-1] && (p[j-1]=="*"||p[j-1]=="?"||p[j-1]==s[i-1]))
            //后来发现不满足 s="ab" p="*"情况，*可以无限匹配,以及  s="a" p="*a*"情况
    		//添加方程  d[i][j] = (d[i-1][j] && p[j-1]=="*") ||(d[i][j-1] && p[j-1]=="*");
            //最终的方程
            // dp[i][j] = (dp[i-1][j-1] && (p[j-1]==anySeq[0]||p[j-1]==anyOne[0]||p[j-1]==s[i-1]));
            // if (dp[i][j] == 0) dp[i][j] = (dp[i-1][j] && p[j-1]==anySeq[0])||(dp[i][j-1] && p[j-1]==anySeq[0]);
            */
    
    
            //程序部分
            int sLen = s.length();
            int pLen = p.length();
            bool dp[sLen + 5][pLen + 5];
            memset(dp, 0, sizeof(dp));
            string anySeq = "*";
            string anyOne = "?";
            //初始化
            dp[0][0] = true;
            if(sLen >= 1) dp[1][0] = false; //其实这行不写也行 
            //如果是*或是连续的*都可以匹配空
    		for(int j = 1; j <= pLen; j++){
    			if(p[j-1] != anySeq[0]) break;
    			dp[0][j] = true;
    		}
            //填充矩阵
            for(int i = 1; i <= sLen; i++){
                for(int j = 1; j <= pLen; j++){
                    dp[i][j] = (dp[i-1][j-1] && (p[j-1]==anySeq[0]||p[j-1]==anyOne[0]||p[j-1]==s[i-1]));
                    if (dp[i][j] == 0) dp[i][j] = (dp[i-1][j] && p[j-1]==anySeq[0])||(dp[i][j-1] && p[j-1]==anySeq[0]);
                }
            }
            return dp[sLen][pLen];
        }
    };

根据上面的情况举个例子验证我们的dp二维数组是否满足我们的期望：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2][]

![20190902190831261.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 3][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/553dd19eaced46ffb6f284de2026141e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/9f3ad16d1e6c4499bbcd8bf13a718e1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/e2ca2e33e437415caa4e40285650e6ba.png
[20190902190831261.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/ac61e563640b4c3ba09af69d2e3aeaa5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/b7176d0b28bd4d029696ea21026fef8d.png