YeungYeah 的乱写地

Wildcard Matching

 Posts  

Problem

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

Solution

函数递归调用

这道题好像在不知道哪里见过，第一反应就是可以递归解决。

实际上，我们需要特别考虑的，就是这个*的匹配情况，对于当前两个字符串，*可以匹配空字符，也可以匹配一个字符，核心的递归式如下：

1
2

isMatch(s,p)=isMatch(s,p[1:]) or isMatch(s[1:],p) if p[0]=='*' else
				p[0] in (s[0],'?') and isMatch(s[1:],p[1:])

方法简单可行，实际上是一个DFS，但是在leetcode上面会超时，用上一个cache缓存后勉强ac。虽然思路简单很容易想到，但递归次数太多，太慢，不是一个好方法。

DP

根据子字符串与子pattern的匹配情况从前往后进行计算.

设dp[i][j]表示前i个匹配pattern可否匹配前j个待匹配字符串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

if p[i-1]=='*':
    dp[i][0]=dp[i-1][0]#能否匹配空字符串取决于前面的pattern
    for j in range(1,len(s)+1):
        dp[i][j]=dp[i-1][j] or dp[i][j-1] or dp[i-1][j-1]
elif p[i]=='?':
    dp[i][0]=False
    for j in range(1,len(s)+1):
        dp[i][j]=dp[i-1][j-1]
else:
    dp[i][0]=False
    for j in range(1,len(s)+1):
        dp[i][j]=s[j-1]==p[i-1] and dp[i-1][j-1]

比较标准的dp方法，运算时间比上面函数递归调用方法快了一半，但执行时间还是很久

相关文章：