CodingTour —

ARTS #100

Algorithm

本周选择的算法题是：Wildcard Matching。

规则

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

• '?' Matches any single character.
• '*' Matches any sequence of characters (including the empty sequence).

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

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

Constraints:

• 0 <= s.length, p.length <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, '?' or '*'.

Solution

暴力 DP：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not s and not p: return True
        if not p: return False
        if not s: return len(p) - p.count('*') == 0
        
        first = s[0]
        if p[0] == '*':
            return any([
                self.isMatch(s[1:], p),
                self.isMatch(s[1:], p[1:]),
                self.isMatch(s, p[1:]),
            ])
        elif p[0] == '?' or p[0] == first:
            return self.isMatch(s[1:], p[1:])
        return False

线性 DP：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
        dp[0][0] = True
        for i in range(len(p)):
            if p[i] != '*':
                break
            dp[0][i+1] = True
        
        for i in range(1, len(s) + 1):
            for j in range(1, len(p) + 1):
                if p[j-1] in {s[i-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]

贪心：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        i, m = 0, len(s)
        j, n = 0, len(p)
        i_star, j_star = -1, -1

        while i < m:
            if j < n and p[j] == '*':
                i_star, j_star = i, j
                j += 1
            elif j < n and (s[i] == p[j] or p[j] == '?'):
                i += 1
                j += 1
            elif i_star > -1:
                i, j = i_star + 1, j_star + 1
                i_star += 1
            else: return False
        while j < n and p[j] == '*': j += 1
        return j == n

Review

How to Write Self-Documenting Code

Self-Documenting 的代码是「Why」与「How」的结合，具备很好的代码可读性。从某种意义上来讲它也是短视的，因为它时刻表达的是当下的做法，但如果 API 设计、文件组织的合理，它可以在一定程度上避免短视。

Tip

周一参加了公司组织的一次外部分享《建立元数据驱动的前端架构》，分享人是飞叔徐飞，收获很大，对元数据驱动、领域模型有了更深刻的认识。

Share

100 周纪念。