[DFS]44. Wildcard Matching

• 分类：DFS/DP
• 时间复杂度: O(m*n) （两种解法都是这个时间复杂度）

44. Wildcard Matching

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).

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

代码：

DFS方法:

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        return self.helper(s,0,p,0,{})
    
    def helper(self,s,i,p,j,memo):
        #如果已经有了就直接返回
        if (i,j) in memo:
            return memo[(i,j)]
        
        #两种出口条件
        if i==len(s):
            for index in range(j,len(p)):
                if p[index]!='*':
                    return False
            return True
        
        if j==len(p):
            return False
        
        #正常情况
        if p[j]!='*':
            matched= (p[j]=='?' or s[i]==p[j]) and self.helper(s,i+1,p,j+1,memo)
        else:
            matched= self.helper(s,i+1,p,j,memo) or self.helper(s,i,p,j+1,memo)
            
        memo[(i,j)]=matched
            
        return matched

DP方法:

class Solution:
    def isMatch(self, s, p):
        if s=="" and (p=="" or p.count('*')==len(p)):
            return True
        elif s=="" or p=="":
            return False

        dp=[[False for i in range(len(p)+1)] for i in range(len(s)+1)]
        dp[0][0]=True

        for i in range(len(s)+1):
            for j in range(len(p)+1):
                if i>0 and j>0:
                    if s[i-1]==p[j-1] or p[j-1]=='?' or p[j-1]=='*':
                        dp[i][j]=dp[i-1][j-1]
                    if p[j-1]=='*':
                        dp[i][j]=dp[i-1][j]
                if j>0 and p[j-1]=="*":
                    dp[i][j]= dp[i][j] or dp[i][j-1]

        return dp[-1][-1]

---

讨论：

1.这道题可以用DFS解

DFS

2.DP之前大体思路没问题，很多细节要扣清楚！！！！细节决定成败！！！细节决定成败！！细节决定成败！重要的事情说三遍！

DP