转载

LeetCode 通配符匹配

LeetCode 通配符匹配

原题链接地址

  • 解题说明

    一开始没有意思到这是到动态规划的题目,走了很多弯路,其实很容易想出来

    只有三种转移条件

    1. ’?’ 匹配 单个字符, 单个字符匹配单个字符
    2. ‘*’ 号匹配零个字符
    3. ‘*’号匹配两个以上个字符
  • Python代码

    class Solution(object):
      def isMatch(self, s, p):
          """ :type s: str :type p: str :rtype: bool """
          #典型的动态规划
          dp = [ [False for i in range(len(s) + 1)] for i in range(len(p) + 1)]
    
          dp[0][0] = True
    
          for i in range(1, len(dp[0])):
              dp[0][i] = False
    
          for i in range(0, len(dp)):
              for j in range(0, len(dp[0])):
                  if i == 0: continue
    
                  if p[i-1] == '*':
                      # '*'号匹配一个字符
                      if j > 0 and dp[i][j-1]:
                          dp[i][j] = True
    
                      # '*'号匹配零个字符
                      if i > 0 and dp[i-1][j]:
                          dp[i][j] = True
                  else:
                      if i > 0 and j > 0:
                          if dp[i-1][j-1] and (p[i-1] == s[j-1] or p[i-1] == '?'):
                              dp[i][j] = True
    
          return dp[len(p)][len(s)]
正文到此结束
本文目录