iT邦幫忙

DAY 17
0

連續30天,挑戰演算法系列 第 17

[Day17] 30 天挑戰演算法 - 萬用字元配對

題目來源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

想法
這題我覺得主要是要測驗對字串的判斷,判斷兩個字串是否相等,但是如果是這樣就太簡單了。所以,這題加上了兩個萬用字元 ?*。所以這題的解法我應該會著重在兩個字串的比對上面。因此,我們先找出會比對失敗的案例:

  1. 如果 pattern 為空字串的話,但字串不是空字串,則比對失敗
  2. 如果 pattern 沒有 * 出現,輸入字串長度又不等於 pattern 長度,則比對失敗

接下來就是要處理 * 這個難纏的符號,因為他有幾個特性:

  1. 他代表任何字元,包含空字元
  2. 在他的前後也可以放任何字元(處理這點比較頭麻煩一點),也就是說假設輸入字串 adsjfbsdjkfc則 pattern*a*b*c*` 和輸入字串比對要是成功的。因為輸入字串的頭是 a, 尾是 c, 中間又有出現 b 。

所以我們必須分別討論以下幾種狀況:

  • * 在最後面:這種情況只要比較 * 之前的有沒有跟 輸入字串 相同即可。
  • * 在最前面:這種情況稍稍麻煩一點,因為要比對的是 輸入字串 的尾端是否跟 pattern 中 * 的尾端相同。
  • * 出現在中間:這個就要綜合以上兩種方式來討論了。

比較方式是以 輸入字串 為主,來跟 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? 比,相等,所以 textIndexpatternIndex 一起前進。
第三次比對時,因為 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;
}      

上一篇
[Day16] 30 天挑戰演算法 - 刪除指定元素
下一篇
[Day18] 30 天挑戰演算法 - 尋找最大(乘)積
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言