写的比较乱，应该还有更clean的
static bool IsMatch(string str, string pattern)
{
if (str == null)
throw new ArgumentNullException("str");
if (string.IsNullOrEmpty(pattern))
throw new ArgumentException("pattern null or emptry.");
return MatchRec(str, pattern, 0, 0);
}
static bool MatchRec(string str, string pattern, int sIndex, int pIndex)
{
if (pIndex == pattern.Length)
{
return sIndex == str.Length;
}
char p = pattern[pIndex];
bool isStar = pIndex < pattern.Length - 1 && pattern[pIndex + 1] == '*';
int nextPIndex = isStar ? pIndex + 2 : pIndex + 1;
bool match; // whether or not current str-char matches current pattern-
char without star
if (sIndex == str.Length)
match = false;
else
{
char c = str[sIndex];
if (p >= 'a' && p <= 'z')
match = c == p;
else if (p == '.')
match = true;
else
throw new FormatException("Pattern in bad format.");
}
if (isStar)
{
if (match) // current match: move either p or s cursor
return MatchRec(str, pattern, sIndex, nextPIndex) || MatchRec(
str, pattern, sIndex + 1, pIndex);
else // current not match: move pattern cursor
return MatchRec(str, pattern, sIndex, nextPIndex);
}
else // must match current and must move both cursors.
return match && MatchRec(str, pattern, sIndex + 1, nextPIndex);
}
Test cases passed:
Debug.Assert(IsMatch("abc", "abc"));
Debug.Assert(!IsMatch("abc", "abcd"));
Debug.Assert(!IsMatch("abc", "abd"));
Debug.Assert(IsMatch("abc", "..."));
Debug.Assert(!IsMatch("abc", ".."));
Debug.Assert(IsMatch("b", "a*b"));
Debug.Assert(IsMatch("ab", "a*b"));
Debug.Assert(IsMatch("aab", "a*b"));
Debug.Assert(IsMatch("aaaaaaaaaab", "a*b"));
Debug.Assert(!IsMatch("aaaaaaaaaa", "a*b"));
Debug.Assert(!IsMatch("cb", "a*b"));
Debug.Assert(!IsMatch("aaaaaaaaaabc", "a*b"));
Debug.Assert(IsMatch("bb", "b.*b"));
Debug.Assert(IsMatch("bab", "b.*b"));
Debug.Assert(IsMatch("b12345b", "b.*b"));
Debug.Assert(IsMatch("", "a*b*c*"));
Debug.Assert(IsMatch("aaaa", "a*b*c*"));
Debug.Assert(IsMatch("bb", "a*b*c*"));
Debug.Assert(IsMatch("ccccc", "a*b*c*"));
Debug.Assert(!IsMatch("d", "a*b*c*"));
