通配符匹配（leetcode_44）
给定一个字符串 (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 = “ab”
输出: true
解释: 第一个 ‘‘ 可以匹配空字符串, 第二个 ‘‘ 可以匹配字符串 “dce”.
示例 5:
输入:
s = “acdcb”
p = “a*c?b”
输入: false
这题我自己没有想出啥好的解决办法，但是leetcode官网给的解决思路我觉得很好，很具有代表性，是两种基本算法的实现，一个是动态规划，一个是回溯。
先说下动态规划的办法，动态规划思路很简单，就是建立一个动态规划表dp，横坐标是s字符串，纵坐标是p字符串，开始这个动态规划表除了（0，0）位置的是true，其他位置的都是false。然后嵌套两层循环，外层循环是p字符串，内层循环是s字符串，我们匹配有一个规则，就是匹配的是单向的，就是每一个匹配除了达到本身能够匹配的条件外，就是两个字符相等或者p字符相应的位置是 “?”，或者p是”*”，还需要匹配的上一个字符也是匹配的。就是动态规划表的dp[pIndex – 1] [sIndex – 1]也是true。我们从遍历开始，发现当前p[pIndex – 1]（就是当前的p的字符，因为pIndex是从1开始的，所以要减一）是 *时，开始遍历dp表dp[pIndex-1]，然后从sIndex=1开始遍历，找到第一个不为false的，然后从这个往后dp[pIndex] [ sIndex – 1]都为true，但是这里需要注意一点，就是遍历结束还有可能是因为pIndex遍历到头了，然后就是dp[pIndex] [ sIndex – 1]要继承dp[pIndex- 1] [sIndex – 1]的状态，然后后面的再开始赋值为true。
然后就是当p为 “？”的时候，这个很简单，直接遍历，然后将dp[pIndex] [sIndex] = dp[pIndex – 1] [sIndex – 1]就行了，因为上一个是true的时候这个也会是true的，然后上一个是false的时候这个也会是false。
再就是一般情况了，恰好两个相等。这个其实和 “?”是差不多的，就是首先判断上一个的情况，然后判断当前两个是相等的，满足这两个条件则我们可以说这个是匹配的。
最后匹配的结果就是dp[plen] [slen]的真假。
class Solution
{
public:
bool isMatch(string s, string p)
{
int plen = p.length();
int slen = s.length();
if (s == p || p == "*")
return true;
if (plen == 0 || slen == 0)
return false;
bool dp[plen + 1][slen + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = true;
for (int pIndex = 1; pIndex < plen + 1; ++pIndex)
{
if (p[pIndex - 1] == '*')
{
int sIndex = 1;
while (sIndex < slen + 1 && !dp[pIndex - 1][sIndex - 1])
sIndex++;
dp[pIndex][sIndex - 1] = dp[pIndex - 1][sIndex - 1];
while (sIndex < slen + 1)
dp[pIndex][sIndex++] = true;
}
else if (p[pIndex - 1] == '?')
{
for (int sIndex = 1; sIndex < slen + 1; sIndex++)
{
dp[pIndex][sIndex] = dp[pIndex - 1][sIndex - 1];
}
}
else
{
for (int sIndex = 1; sIndex < slen + 1; sIndex++)
{
dp[pIndex][sIndex] = dp[pIndex - 1][sIndex - 1] && p[pIndex - 1] == s[sIndex - 1];
}
}
}
return dp[plen][slen];
}
};
再就是另外一种回溯法，回溯法的思路很简单，这个不是下标单向增加的，s数组的下标有可能返回。
我们就一直向后匹配，遇到 “*”，记录此时s和p数组的下标分别为sTmpIdx 和startIdx，记录后继续后移p下标匹配不用移s的下标，当出现不匹配的情况，开始回溯，回溯的方法为，将sIndx=sTmpIdx + 1，将pIndx = startIdx + 1，然后更新sTmpIdx = sIndx，然后继续下一轮匹配，这么干的目的是我们一直在后移sIndx，就是用 * 匹配那些之前匹配出错的数组，直到找到能正确匹配的下标顺序。
在循环体体里面，我们是以sIndx作为下标循环的，在循环里面若pIndx先到plen的时候我们会将匹配退回到上一个出现*的地方，然后继续匹配。
判断是否匹配成功的方法为，在我们sIndx下标移到最后后，退出循环，然后继续循环pIndx一直到plen，在这中间只要出现一个不是 * 的元素那么就判断循环失败。pIndx循环完后返回true表示能够正确匹配。
class Solution
{
public:
bool isMatch(string s, string p)
{
int slen = s.length(), plen = p.length();
int sIdx = 0, pIdx = 0;
int startIdx = -1, sTmpIdx = -1;
while (sIdx < slen)
{
if (pIdx < plen && (p[pIdx] == '?' || p[pIdx] == s[sIdx]))
{
pIdx++;
sIdx++;
}
else if (pIdx < plen && p[pIdx] == '*')
{
startIdx = pIdx;
sTmpIdx = sIdx;
pIdx++;
}
else if (startIdx == -1)
{
return false;
}
else
{
pIdx = startIdx + 1;
sIdx = sTmpIdx + 1;
sTmpIdx = sIdx;
}
}
for (int i = pIdx; i < plen; ++i)
if (p[i] != '*')
return false;
return true;
}
};