这是leetcode上面的第十题，前面的第五题和第六题没有做，因为感觉字符串处理还是弱项，打算之后一起做，而再后面的第七题，第八题，第九题，比较简单无脑，就不记录了。
问题描述
. Matches any single character.
* Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
想法与实现
首先这道题其实不是正宗的正则表达式匹配问题，一开始我是把它当正则来做的，但是在处理*的时候遇到了一些问题。这里的*的意思并不是可以匹配0+个字符，而是对于前面的那个字符，可以匹配0+个。比如在example里面的最后一个用例，isMatch("aab", "c*a*b") → true，其中的c*a*b，他的意思是这样的：一个有N个c，N个a，一个b的字符串。这其实处理起来，比正规的正则还是要更加麻烦一些的。
标准正则
那就先看看如何实现对于标准的正则的匹配吧。第一个想法是，先正则表达式转成NFA，然后转成DFA，用DFA去识别字符串。是受编译原理荼毒太深= =这样实现太复杂了。后来的想法就是，利用这种状态转换的思想，在字符串p中的一个字符就是一种状态，然后让字符串s一个个去匹配p，如果字符不是*，那就状态转移至下一个字符，如果是的话，就穷举所有情况，看有没有情况可以匹配到p的最后一个状态的同时也匹配到s中的最后一个字符，那么可以就说明匹配成功，匹配的过程有点类似深度优先搜索。实现的代码大概是这样的~
bool isMatch(const char *s, const char *p) {
string source = s;
string pattern = p;
return match(source, pattern, 0, 0);
}
bool match(string s, string p, int posS, int posP)
{
if (posS == s.size() && posP == p.size())
return true;
else if ((posS == s.size() && posP < p.size()) || (posS < s.size() && posP == p.size()))
return false;
if (p[posP] != '*')
{
if (p[posP] == '.' || p[posP] == s[posS])
{
posS++;
posP++;
return match(s, p, posS, posP);
}
}
else
{
bool stayInTheState = match(s, p, posS + 1, posP);
bool jumpToNextSatte = match(s, p, posS + 1, posP + 1);
if (stayInTheState == true || jumpToNextSatte == true)
return true;
else
return false;
}
}
代码大致是这样，整体应该还是比较容易理解的~可能会有小bug，但是大题思路是这样的。
本题的做法
本题中，跟正则唯一有不同的地方在于*的不同，处理起来会稍微麻烦一些，但是整体的思路还是跟标准的正则差不多~现在的情况下，处理*需要考虑两个字符，那么就把这两个字符当成一个状态，就可以了。
bool isMatch(const char *s, const char *p) {
string source = s;
string pattern = p;
return match(source, pattern, 0, 0);
}
bool match(string s, string p, int posS, int posP)
{
if (posP == p.size())
return posS == s.size();
if (posP + 1 == p.size() && p[posP + 1] != '*')
{
if (p[posP] == '.' || p[posP] == s[posS])
{
posS++;
posP++;
return match(s, p, posS, posP);
}
else
return false;
}
else if (p[posP + 1] != '*')
{
if (p[posP] == '.' || p[posP] == s[posS])
{
posS++;
posP++;
return match(s, p, posS, posP);
}
else
return false;
}
else
{
while ((p[posP] == s[posS]) || (p[posP] == '.' && posS < s.size()))
{
if (match(s, p, posS, posP + 2))
return true;
posS++;
}
return match(s, p, posS, posP + 2);
}
}
上面的实现，用时还是比较长的，会有440MS，可以做的提高是Cache，缓存每次的结果，因为这些结果都是不会变化的，所以这样就不需要每次都递归求解。在官方给的Tag里还有DP，不知道DP是怎么一种解法。