Wildcard Matching :
給定一個字符串跟pattern，看這個字符串可不可以match pattern，包含“？” 及 ‘*’
“？” 匹配任何單個字符 ( 不包含空字符)。
‘*’ 匹配任何長度字符序列（包括空序列）。
Python
動態規劃解題:
class Solution:
def isMatch(self, s, p):
dp = [[False for _ in range(len(p)+1)] for i in range(len(s)+1)]
dp[0][0] = True
#當s為空的時候，可能滿足'*'，而且要確定前一個數不是'*'，才返回true
for j in range(1, len(p)+1):
if p[j-1] != '*':
break
dp[0][j] = True
for i in range(1, len(s)+1):
for j in range(1, len(p)+1):
#當 p上一個字符爲'？'或者p上一個字符等於s上一個字符，則當前值與 上一位相同
if p[j-1] == '?' or s[i-1] == p[j-1]:
dp[i][j] = dp[i-1][j-1]
#p上一個字符爲'*'時，則當前值等於p往後走一位或者s往後走一位
elif p[j-1] == '*':
dp[i][j] = dp[i-1][j] or dp[i][j-1]
return dp[-1][-1]DFS求解 : 動態規劃類似
class Solution:
def isMatch(self, s: str, p: str) -> bool:
def dfs(i, j):
if j == len(p):
return i == len(s)
if i < len(s) and (s[i] == p[j] or p[j] == '?'): # Match Single character
return dfs(i + 1, j + 1)
if p[j] == '*':
return dfs(i, j + 1) or i < len(s) and dfs(i + 1, j) # Match zero or one or more character
return False
return dfs(0, 0)C++
Bottom up法:
dp[0][0]=true or 1。這是因為如果模式和匹配字符串的長度為0，則它們相等或匹配。
我們可以填充 dp 的第一行。 DP 的第一行告訴我們匹配的字符串長度為零，然後直到模式匹配空字符串的那一列。 所以我們知道只有當那個點的模式字符是’‘時才會發生，如果除了’‘之外還有其他任何東西，那麼我們就會中斷。
現在，我們可以開始填充 dp 的第二行，如果模式在 j-1 處是 ‘ * ‘，那麼我們可以使用它來匹配，在這種情況下它將等於 dp[i-1][j] 和 如果我們對’*’使用空字符串，那麼它等於dp[i][j-1]。
如果 j-1 處的模式不是 ‘ * ‘ 那麼我們需要檢查字符是否相等或 j-1 處的模式字符是否為 ‘ ? ‘ 然後 dp[i][j] =dp[i-1][j-1];
class Solution {
public:
bool isMatch(string s, string p) {
if(p.length()==0)
return (s.length()==0);
vector<vector<int>> dp(s.length()+1,vector<int>(p.length()+1,0));
dp[0][0]=1;
for(int i=1;i<=p.length();i++)
{
if(p[i-1]=='*')
dp[0][i]=1;
else
break;
}
for(int i=1;i<=s.length();i++)
{
for(int j=1;j<=p.length();j++)
{
if(p[j-1]=='*')
{
dp[i][j]=dp[i-1][j] || dp[i][j-1];
}
else if(p[j-1]==s[i-1] || p[j-1]=='?')
{
dp[i][j]=dp[i-1][j-1];
}
}
}
return dp[s.length()][p.length()];
}
};