題目來源：Wildcard Matching
問題：
實作一個以支援 ? 及 \* 配對的函式，詳細說明如下
?代表任何單一字元
\*代表任何字串 （包含空字串)
這個配對必須涵蓋全部的輸入字串（不能只配對部份）此函式用不同語言實作的名稱如下：
C# -> public bool IsMatch(String s, String p) {}
C++ -> bool isMatch(const char *s, const char *p){}
Java -> public boolean isMatch(String s, String p){}
Python -> def isMatch(self, s, p):
例子
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "\*") → true
isMatch("aa", "a\*") → true
isMatch("ab", "?\*") → true
isMatch("aab", "c*a*b") → false
想法
這題我覺得主要是要測驗對字串的判斷，判斷兩個字串是否相等，但是如果是這樣就太簡單了。所以，這題加上了兩個萬用字元 ? 及 *。所以這題的解法我應該會著重在兩個字串的比對上面。因此，我們先找出會比對失敗的案例：
接下來就是要處理 * 這個難纏的符號，因為他有幾個特性：
則 pattern*a*b*c*` 和輸入字串比對要是成功的。因為輸入字串的頭是 a, 尾是 c, 中間又有出現 b 。所以我們必須分別討論以下幾種狀況：
比較方式是以 輸入字串 為主，來跟 pattern 做比較，用一個 while 迴圈從 輸入字串 的第一個字元跑到最後一個字元，所以基本上 輸入字串 的字元數量應該是會大於或等於 pattern 的數量，所以基本上 輸入字串 掃完，pattern 也要掃完才對，不過，如果以這個想法下去寫，應該會過不了測試程式，因為，* 這個字元也代表著 空字串，因此，假設是錯誤的。舉例來說：
輸入字串= 3; pattern= *?* 或 輸入字串 =abc; pattern= *a*b*c*
上面的例子，pattern 字元數都大於 輸入字串。所以就必須在掃完輸入字串後，在接著判斷 pattern 能不能掃到最後。（也就是判斷 * 符號的意思啦），再去判斷輸入字串有沒有完全符合 pattern，若有符合，比較過的 patternIndex 就會等於 pattern字元數 了。
一開始，先寫下題目所給的函式名稱跟輸入參數：
public bool IsMatch(string text, string pattern){}
接著是我們會用到的 index 來紀錄目前掃到哪一個字元：
int textIndext = 0;
int patternIndex = 0;
有了 index 之後，第一步就是寫下主要的迴圈，主要的目的就是要從 數入字串 第一個字元走到最後一個字元，好讓這些字元可以跟 pattern 做比較，但由於 pattern 字元數可能大於也可能小於 輸入字串，所以我們在這迴圈內也必須處理一下 pattern 的字元數，以免超出他的範圍產生 OutOfIndexException。當迴圈結束後，再處理一下 pattern 最後可能是 * 符號的狀況。
int textIndex = 0;
int patternIndex = 0;
while (textIndex < text.Count())
{
bool isEndOfPattern = patternIndex == pattern.Count();
}
while (patternIndex < pattern.Count() && pattern[patternIndex] == '*')
patternIndex++;
return patternIndex == pattern.Count();
有了主要的架構之後，首先我們先來處理最簡單的狀況，也就是當 pattern 裡沒有 * 符號時的情形，但可以有 ?。因為只要出現 ? 就代表比對成功，連比都不用比，很容易。
while (textIndex < text.Count())
{
bool isEndOfPattern = patternIndex == pattern.Count();
if (!isEndOfPattern && IsTextEqualPatternOrQuestionMark(text[textIndex], pattern[patternIndex]))
{
textIndex++;
patternIndex++;
} else
{
return false;
}
}
下一步我們就要考慮，* 出現之後要怎麼處理。
假設我們的 輸入字串為 = 11ab11ab11ab; pattern = *ab
但因為我們是從前面比過去，所以我們就必須要記住 * 出現的位置，因此我們要多一個 index <span style="color:#FF0000"><span style="background-color:#D3D3D3">asteriskIndex</span></span>來記。
int asteriskIndex = -1; // 用-1來表示 * 符號沒出現過
...(略)
else if (!isEndOfPattern && pattern[patternIndex] == '*')
{
asteriskIndex = patternIndex;
patternIndex += 1;
}
else if (asteriskIndex != -1 )
{
patternIndex = asteriskIndex + 1;
textIndex += 1;
}
else
{
return false;
}
上面加入的判斷式主要是針對 * 出現後，這時使用 asteriskIndex 來記住 * 出現的位置，patternIndex 則是要繼續往下一格，那是因為要比對 * 後面的字串跟 輸入字串 最後的字串是否相等。如果往下比 字元不相等，pattern 也不是 * 則，pattern 會等於 pattern = asteriskIndex + 1`，一直停留在這裡，直到比完為止。這時候因為 pattern 所停留的位置不是 *，也沒有走過最後一個字元，所以 patternIndex == pattern.Count(); 是絕對不會成立。
截至目前為止我們來看一下完整的程式碼：
public static bool IsMatch(string text, string pattern)
{
int textIndex = 0;
int patternIndex = 0;
int asteriskIndex = -1;
while (textIndex < text.Count())
{
bool isEndOfPattern = patternIndex == pattern.Count();
if (!isEndOfPattern && IsTextEqualPatternOrQuestionMark(text[textIndex], pattern[patternIndex]))
{
textIndex++;
patternIndex++;
}
else if (!isEndOfPattern && pattern[patternIndex] == '*')
{
asteriskIndex = patternIndex;
patternIndex += 1;
}
else if (asteriskIndex != -1) // 表示前面有出現過 *
{
patternIndex = asteriskIndex + 1;
textIndex += 1;
continue;
}
else
{
return false;
}
}
while (patternIndex < pattern.Count() && pattern[patternIndex] == '*')
patternIndex++;
return patternIndex == pattern.Count();
}
public static bool IsTextEqualPatternOrQuestionMark(char character, char pattern)
{
if (character == pattern || pattern == '?')
return true;
return false;
}
然後測試一下，居然發現有個問題，那就是當 輸入字串 = hi; pattern = *? 時會出錯。
那就來驗證一下吧，看是哪裡出了問題。
原來是當地一次比對的時候，因為 pattern 是 * 所以，textIndex 會停留在原本的位置，只有 patternIndex 會前進。
第二次比對時，h 跟 ? 比，相等，所以 textIndex 與 patternIndex 一起前進。
第三次比對時，因為 patternIndex 已經到最後，所以會進入到 前有有出現過 * 那個判斷式，可能判斷式為了讓 *xxx 這種類型的 pattern 可以順利比對尾端，所以他又把 patternIndex 調回 * 出現過得後一格。（也就是目前的 ?)，所以當然比對失敗囉。
因此，我們可以試著再加一個 index, 紀錄當 * 出現時的 textIndex 位置。就叫做 asteriskTextIndex
當 * 出現時，就先把 textIndex 目前的位置給記下來。
當後面比對失敗，跑到有 * 出現過的那個 method 時，就先把 asteriskTextIndex + 1 再給 textIndex，以補償因為差 1 而比對失敗，也就是比對 * 後面的字元。
public static bool IsMatch(string text, string pattern)
{
int textIndex = 0;
int patternIndex = 0;
int asteriskIndex = -1;
int asteriskTextIndex = 0;
while (textIndex < text.Count())
{
bool isEndOfPattern = patternIndex >= pattern.Count();
if (!isEndOfPattern && IsTextEqualPatternOrQuestionMark(text[textIndex], pattern[patternIndex]))
{
textIndex++;
patternIndex++;
}
else if (!isEndOfPattern && pattern[patternIndex] == '*')
{
asteriskIndex = patternIndex;
patternIndex += 1;
asteriskTextIndex = textIndex;
}
else if (asteriskIndex != -1) // 表示前面有出現過 *
{
textIndex = ++asteriskTextIndex;
patternIndex = asteriskIndex + 1;
}
else
{
return false;
}
}
while (patternIndex < pattern.Count() && pattern[patternIndex] == '*')
patternIndex++;
return patternIndex == pattern.Count();
}
public static bool IsTextEqualPatternOrQuestionMark(char character, char pattern)
{
if (character == pattern || pattern == '?')
return true;
return false;
}
iThome鐵人賽
看影片追技術