本篇圖文是LSGO軟件技術團隊組織的 第二期基礎算法（Leetcode）刻意練習訓練營 的打卡任務。本期訓練營采用分類別練習的模式，即選擇了五個知識點（數組、鏈表、字符串、樹、貪心算法），每個知識點選擇了 三個簡單、兩個中等、一個困難 等級的題目，共計三十道題，利用三十天的時間完成這組刻意練習。
本次任務的知識點：貪心算法
貪心算法（greedy algorithm），又稱貪婪算法，是一種在每一步選擇中都采取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是最好或最優的算法。
貪心算法在有最優子結構的問題中尤為有效。最優子結構的意思是局部最優解能決定全局最優解。簡單地說，問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解。
貪心算法與動態規劃的不同在于它對每個子問題的解決方案都做出選擇，不能回退。動態規劃則會保存以前的運算結果，并根據以前的結果對當前進行選擇，有回退功能。
題號：44
難度：困難
https://leetcode-cn.com/problems/wildcard-matching/
給定一個字符串(s) 和一個字符模式(p) ，實現一個支持'?'和'*'的通配符匹配。
'?' 可以匹配任何單個字符。
'*' 可以匹配任意字符串（包括空字符串）。
兩個字符串完全匹配才算匹配成功。
說明:
s可能為空，且只包含從a-z的小寫字母。
p可能為空，且只包含從a-z的小寫字母，以及字符?和*。
示例 1:
輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個字符串。
示例 2:
輸入:
s = "aa"
p = "*"
輸出: true
解釋: '*' 可以匹配任意字符串。
示例 3:
輸入:
s = "cb"
p = "?a"
輸出: false
解釋: '?' 可以匹配 'c', 但第二個 'a' 無法匹配 'b'。
示例 4:
輸入:
s = "adceb"
p = "*a*b"
輸出: true
解釋: 第一個 '*' 可以匹配空字符串, 第二個 '*' 可以匹配字符串 "dce".
示例 5:
輸入:
s = "acdcb"
p = "a*c?b"
輸出: false
示例 6:
輸入：
"abefcdgiescdfimde"
"ab*cd?i*de"
輸出：true
示例 7:
輸入：
"aaaa"
"***a"
輸出：true
第一種：雙索引法
我們用i和j分別標記s和p的第一個字符下標，即都初始化為0。用istart和jstart分別標記s和p中'*'匹配過的位置，即初始化為-1。
和普通字符串匹配的思路差不多，已經匹配成功的部分就不再考慮了，所以要用i和j標記當前正在比較的字符；但是最近匹配過的'*'可能會被重復使用去匹配更多的字符，所以我們要用istart和jstart分別標記s和p中最近匹配過'*'的位置。
如果i和j標記的字符正好相等或者j字符是'?'匹配成功，則"移除"i和j元素，即自增i、j。
否則如果j字符是'*'依然可以匹配成功，則用istart和jstart分別標記i元素和j元素，自增j。
再否則如果istart>-1說明之前匹配過''`，因為`''可以匹配多個字符，所以這里要再次利用這個最近匹配過的'*'匹配更多的字符，移動i標記istart的下一個字符，再讓istart重新標記i元素，同時移動j標記jstart的下一個字符。
上述三種情況都不滿足，則匹配失敗，返回false。
最后當s中的字符都判斷完畢，則認為s為空，此時需要p為空或者p中只剩下星號的時候，才能成功匹配。
執行結果：通過
執行用時：92 ms, 在所有 C# 提交中擊敗了 95.00% 的用戶
public class Solution
{
public bool IsMatch(string s, string p)
{
//若正則串p為空串，則s為空串匹配成功，s不為空串匹配失敗。
if (string.IsNullOrEmpty(p))
return string.IsNullOrEmpty(s) ? true : false;
int i = 0, j = 0, istart = -1, jstart = -1, plen = p.Length;
//判斷s的所有字符是否匹配
while (i < s.Length)
{
//三種匹配成功情況以及匹配失敗返回false
if (j < plen && (s[i] == p[j] || p[j] == '?'))
{
i++;
j++;
}
else if (j < plen && p[j] == '*')
{
istart = i;
jstart = j;
j++;
}
else if (istart > -1)
{
i = istart + 1;
istart = i;
j = jstart + 1;
}
else
{
return false;
}
}
//s中的字符都判斷完畢，則認為s為空
//此時需要p為空或者p中只剩下星號的時候，才能成功匹配。
//如果p中剩余的都是*，則可以移除剩余的*
while (j < plen && p[j] == '*')
{
j++;
}
return j == plen;
}
}
第二種：動態規劃
dp數組的含義：dp[i,j]意思是s的前i個元素能否被p的前j個元素成功匹配。
知道了dp數組的含義之后，我們就知道了初始化細節：
bool類型的dp數組，大小是[s.length+1,p.length+1]，因為存在s前0個字符和p前0個字符的情況，即s為空串或p為空串。
dp[0,0]一定是true，因為s空串和p空串是可以匹配成功的；dp[1,0] ~ dp[s.length,0]一定都是false，因為s不為空串而p為空串是不能匹配成功的。
dp[0,1] ~ dp[0,p.length]當s為空串的時候，而p不是空串的時候，當且僅當p的j字符以及前面都為'*'才為true。
dp[s.length,p.length]就得到了s和p最終的匹配情況。
有了上述理解之后，就可以初始化dp數組了。
然后填寫dp數組剩余部分即可，狀態轉移方程：
當s[i] == p[j]或者p[j] == '?'，則dp[i,j] = dp[i-1,j-1]?？梢岳斫鉃楫斍白址晒ζヅ浜螅恍枰紤]之前的字符串是否匹配即可。
當p[j] == ''`，則`dp[i,j] = dp[i-1,j] || dp[i,j-1]`。可以理解為當字符為`''的時候會出現兩種情況，第一種是''`需要作為一個字母與`s[i]`進行匹配；第二種是`''需要作為空字符(即不需要'*'可以直接"移除")，所以dp[i,j-1]；用邏輯或將兩種情況連接，是因為只要有一種情況可以匹配成功則當前匹配成功，有點暴力算法的感覺。
最后當s[i] !=p [j] && p[j] != '*'，dp[i,j] = false。這步可以省略，因為dp數組元素的默認值就是false，所以不必要進行顯式的賦值為false。
有了上面的理解，我們就可以寫代碼了。
執行結果：通過
執行用時：112 ms, 在所有 C# 提交中擊敗了 62.50% 的用戶
class Solution
{
public bool IsMatch(string s, string p)
{
if (string.IsNullOrEmpty(p))
return string.IsNullOrEmpty(s) ? true : false;
int slen = s.Length, plen = p.Length;
bool[,] dp = new bool[slen + 1, plen + 1];
//初始化dp數組
//dp[1][0]~dp[s.length][0]默認值flase不需要顯式初始化為false
dp[0, 0] = true;
//dp[0][1]~dp[0][p.length]只有p的j字符以及前面所有字符都為'*'才為true
for (int j = 1; j <= plen; j++)
{
dp[0, j] = p[j - 1] == '*' && dp[0, j - 1];
}
//填寫dp數組剩余部分
for (int i = 1; i <= slen; i++)
{
for (int j = 1; j <= plen; j++)
{
char si = s[i - 1], pj = p[j - 1];
if (si == pj || pj == '?')
{
dp[i, j] = dp[i - 1, j - 1];
}
else if (pj == '*')
{
dp[i, j] = dp[i - 1, j] || dp[i, j - 1];
}
}
}
return dp[slen, plen];
}
}
