引言

Task30.

Leetcode第44题 难度：困难 题目概述： 给定一个字符串 s 和一个字符模式 p ，实现一个支持 ? 和 * 的通 配符匹配。 ? 可以匹配任何单个字符。 * 可以匹配任意字符串（包括空字符串）。 两个字符串完全匹配才算匹配成功。 说明: s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。 示例 1: 输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。 示例 2: 输入: s = "aa" p = "*" 输出: true 解释: * 可以匹配任意字符串。 示例 3: 输入: s = "cb" p = "?a" 输出: false 解释: ? 可以匹配 c, 但第二个 a 无法匹配 b。 示例 4: 输入: s = "adceb" p = "*a*b" 输出: true 解释: 第一个 * 可以匹配空字符串, 第二个*可以匹配字符串"dce" 示例 5: 输入: s = "acdcb" p = "a*c?b" 输入: false

题解思路

1.超时的递归

看到这道题，第一反应就是用递归，大笔一挥，代码出来了，顺便也超时了。因为输入的字符串很长的时候，递归深度太大，就会引起超时。

class Solution {
          
   
    public boolean isMatch(String s, String p) {
          
   
        if(s.isEmpty())
            return p.matches("\**"); 
        else if(p.isEmpty())
            return false;
        char s0=s.charAt(0);
        char p0=p.charAt(0);
        boolean first= p0==* || p0==? ||s0==p0;
        if(p0==*)
            return isMatch(s,p.substring(1)) || //*代表零个字符
                   isMatch(s.substring(1),p.substring(1)) || //*代表一个字符
                   isMatch(s.substring(1),p); //*代表多个字符
        else
            return first && isMatch(s.substring(1),p.substring(1));
    }
}

提交记录

2.回溯（参考题解）

整个问题中让人头疼的其实只是 *号的匹配个数问题，那么我们可以依次“尝试”，对于 *号（如果是连续的 *****号，只取最后一个进行假设），先假设它匹配 0 个字符，匹配剩下的 pattern,如果错误，回到假设的 *号处，假设它匹配 1 个字符，以此类推，直到 s 匹配完成。

时间复杂度：O( s*log( p ) )

class Solution {
          
   
        public boolean isMatch(String s, String p) {
          
   
        int pLen = p.length();
        int pS=0, pP=0;
        int pStar = -1, pStr = -1;
        while (pS<s.length()) {
          
   
            if (pP < pLen && (p.charAt(pP) == ? || p.charAt(pP) == s.charAt(pS))){
          
   
                ++pS;
                ++pP;
            }
            //如果有*,则记录可回溯的位置并让它代表零个字符
            else if (pP < pLen && p.charAt(pP) == *) {
          
    
                pStar = pP;
                pStr = pS;
                ++pP;
            }
            //不匹配且没有可回溯的*,返回false
            else if (pStar==-1) 
                return false;
            //不匹配但是具有可回溯的*,则让*匹配更多的字符
            else {
          
    
                pP = pStar + 1;
                pS = pStr + 1;
                pStr = pS;
            }
        }
        //偷懒使用了正则表达式,速度会变慢
        return p.substring(pP).matches("\**"); 
    }
}

提交记录

3.动态规划

说实话，接触了这么多动态规划的题目，虽然我看得出来这道题可以用 “动态规划” 解决，自己上手的时候就一头雾水，所以就不丢人现眼了。