https://leetcode-cn.com/problems/wildcard-matching/
# -*- coding:utf-8 -*- class Solution(object): def isMatch(self, s, p): """ :type s: str :type p: str :rtype: bool """ sn = len(s) pn = len(p) dp = [[False] * (pn + 1) for _ in range(sn + 1)] dp[0][0] = True for j in range(1, pn + 1): if p[j - 1] == "*": dp[0][j] = dp[0][j - 1] for i in range(1, sn + 1): for j in range(1, pn + 1): if (s[i - 1] == p[j - 1] or p[j - 1] == "?"): dp[i][j] = dp[i - 1][j - 1] elif p[j - 1] == "*": dp[i][j] = dp[i - 1][j] or dp[i][j - 1] return dp[-1][-1] if __name__ == '__main__': s = 'acdcb' p = 'a*c?b' print(Solution().isMatch(s, p))
思路:不得不说,动态规划确实需要多做做题,这道题明明知道是动态规划,可是中间状态依然找不到,这种问题前面已经出现过了。
如果i,j匹配则当前状态等于i-1,j-1的状态,如果是*则说明当前的状态是i-1,j(*匹配空)或者i,j-1(*匹配任意字符串)中的一个。
动态规划列表如下

0 条评论