[Leetcode][第44题][JAVA][通配符匹配][贪心][动态规划]

浅浅的花香味﹌ 2023-02-23 05:02 58阅读 0赞

#### 【问题描述】\[困难\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

![在这里插入图片描述][20200705133010919.png]

###### 1. 动态规划 ######

第 1 步：设计状态  
dp\[i\]\[j\]dp\[i\]\[j\] 表示字符串 ss 的前 ii 个字符和模式 pp 的前 jj 个字符是否能匹配  
第 2 步：状态转移方程  
![在这里插入图片描述][20200705133020590.png]  
第 3 步：考虑初始化  
boolean\[\]\[\] dp = new boolean\[m + 1\]\[n + 1\];  
![在这里插入图片描述][20200705133041421.png]  
第 4 步：考虑输出  
dp\[m\]\[n\];  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度：O(MN) 空间复杂度：O(MN)**  
![在这里插入图片描述][20200705133815713.png]

public boolean isMatch(String s, String p) { 
            int m = s.length();
            int n = p.length();
            boolean[][] dp = new boolean[m + 1][n + 1];
            dp[0][0] = true;
            for(int i=1 ;i<=n;i++){ 
                if(p.charAt(i-1)== '*'){ 
                    dp[0][i]=true;
                }else{ 
                    break;
                }
            }
    
            for(int i=1;i<=m;i++){ 
                for(int j=1;j<=n;j++){ 
                    if(p.charAt(j-1)=='*'){ 
                        dp[i][j]= dp[i-1][j]|dp[i][j-1]; 
                    }else if((p.charAt(j-1) == s.charAt(i-1))||(p.charAt(j-1)=='?')){ 
                         dp[i][j]= dp[i-1][j-1]; 
                    }
                }
            }
            return dp[m][n];
        }

###### 2. 贪心 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

// 我们用 sIndex 和 pIndex 表示当前遍历到 s 和 p 的位置
    // 此时我们正在 s 中寻找某个 u_i
    // 其在 s 和 p 中的起始位置为 sRecord 和 pRecord
    
    // sIndex 和 sRecord 的初始值为 0
    // 即我们从字符串 s 的首位开始匹配
    sIndex = sRecord = 0
    
    // pIndex 和 pRecord 的初始值为 1
    // 这是因为模式 p 的首位是星号，那么 u_1 的起始位置为 1
    pIndex = pRecord = 1
    
    while sIndex < s.length and pIndex < p.length do
        if p[pIndex] == '*' then
            // 如果遇到星号，说明找到了 u_i，开始寻找 u_i+1
            pIndex += 1
            // 记录下起始位置
            sRecord = sIndex
            pRecord = pIndex
        else if match(s[sIndex], p[pIndex]) then
            // 如果两个字符可以匹配，就继续寻找 u_i 的下一个字符
            sIndex += 1
            pIndex += 1
        else if sRecord + 1 < s.length then
            // 如果两个字符不匹配，那么需要重新寻找 u_i
            // 枚举下一个 s 中的起始位置
            sRecord += 1
            sIndex = sRecord
            pIndex = pRecord
        else
            // 如果不匹配并且下一个起始位置不存在，那么匹配失败
            return False
        end if
    end while
    
    // 由于 p 的最后一个字符是星号，那么 s 未匹配完，那么没有关系
    // 但如果 p 没有匹配完，那么 p 剩余的字符必须都是星号
    return all(p[pIndex] ~ p[p.length - 1] == '*')

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
**时间复杂度：O(MN) 空间复杂度：O(MlogN)**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]

class Solution { 
        public boolean isMatch(String s, String p) { 
            int sRight = s.length(), pRight = p.length();
            while (sRight > 0 && pRight > 0 && p.charAt(pRight - 1) != '*') { 
                if (charMatch(s.charAt(sRight - 1), p.charAt(pRight - 1))) { 
                    --sRight;
                    --pRight;
                } else { 
                    return false;
                }
            }
    
            if (pRight == 0) { 
                return sRight == 0;
            }
    
            int sIndex = 0, pIndex = 0;
            int sRecord = -1, pRecord = -1;
            
            while (sIndex < sRight && pIndex < pRight) { 
                if (p.charAt(pIndex) == '*') { 
                    ++pIndex;
                    sRecord = sIndex;
                    pRecord = pIndex;
                } else if (charMatch(s.charAt(sIndex), p.charAt(pIndex))) { 
                    ++sIndex;
                    ++pIndex;
                } else if (sRecord != -1 && sRecord + 1 < sRight) { 
                    ++sRecord;
                    sIndex = sRecord;
                    pIndex = pRecord;
                } else { 
                    return false;
                }
            }
    
            return allStars(p, pIndex, pRight);
        }
    
        public boolean allStars(String str, int left, int right) { 
            for (int i = left; i < right; ++i) { 
                if (str.charAt(i) != '*') { 
                    return false;
                }
            }
            return true;
        }
    
        public boolean charMatch(char u, char v) { 
            return u == v || v == '?';
        }
    }

#### 【总结】 ####

###### 1.动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2.贪心 字符串匹配 细心分情况 ######

转载链接：https://leetcode-cn.com/problems/wildcard-matching/solution/tong-pei-fu-pi-pei-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200706105849667.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200705133010919.png]: https://img-blog.csdnimg.cn/20200705133010919.png
[20200705133020590.png]: https://img-blog.csdnimg.cn/20200705133020590.png
[20200705133041421.png]: https://img-blog.csdnimg.cn/20200705133041421.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200706105936841.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200705133815713.png]: https://img-blog.csdnimg.cn/20200705133815713.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200705133638623.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200705133713989.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200705133749222.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70