[LeetCode] 更快的 Recursion?! 用 Divide-and-Conquer 解 #10 Regular Expression Matching

-

這題幾乎所有解答不是用從左往右的 Recursion 來解就是 DP 解。但我這次要用從中間開始的 Recursion 來追上 DP 的速度。

直覺的比喻

寶寶最愛玩的形狀配對盒今天要來幫助我們解題了! 為什麼我會想到用這個比喻就是之前看了一個 Reddit "Devs watching QA test the product" 一個幽默影片裡面就惡搞寶寶最愛玩的形狀配對盒子，把所有積木都丟到正方形孔去。

假設今天我們要把 "aaabcdbbc" 這串 s 測試能不能 match 一段 regular expression "a*b.*b*c"。

有 "*" 符號的我們就用一個什麼都裝的下的積木盒來代表、沒有 "*" 符號的我們用只能裝下 1 個積木的積木盒代表:


所以題目問的就是: 我們可以從左往右依序丟積木，符合積木盒上的數目要求嗎?

這樣丟就可以了:


什麼時候會失敗? 你沒丟完的時候，別想把積木藏起來:


或是有積木盒沒丟到數目要求:


但不是每一個積木盒都要丟，"x*" 類型的積木盒你不丟也無所謂:


為何不能遇到 * 就狂丟

LeetCode 第一個解答是從左往右丟積木，遇到 "x*" 的積木盒，要嘛就是丟一個要嘛就是不丟，因為後面會發生什麼事還不知道，都試試看再說。

為什麼我們遇到 "x*" 會沒辦法決定要不要丟? 舉個例子像是 s = "aaa", p = "a*a"，如果你把 3 個 "a" 都丟到 p[0:1] 的 "a*" 那最後面的 "a" 要誰來 match? 這時候 greedy 反而會失敗，所以你只能試所有的可能性。

各個擊破 (Divide and Conquer)

有點像 Quicksort，我們先取中間的 character 找到適合的積木盒丟下去:


不過要記得每個可能性都還是要試過。要從左往右或隨機挑就隨便你了。

接著我們問說左邊剩下的 input string 可以被 match 嗎?


再問右邊可以被 match 嗎?


就這樣 Recursive 跑下去，我們只要判斷最終結束時候的情況就做完了:

  • input string 沒了，但還有 pattern: 如果積木盒都是無底洞的類型才算 true
  • input string 還有，但 pattern 空了: 積木還有剩，所以是 false
  • 中間的 character 找不到適合的積木盒裝: 積木還有剩，所以還是 false

比較要注意的地方就是 pattern 的部分遇到 "x*" 無底洞的積木盒要記得在 recursion 呼叫保留下來，因為他當然還可以繼續丟，但遇到只能放一個東西的積木盒就不要保留下來了。

如果我們把 recursion 的樹狀架構畫出來就會長這樣:


先來寫測試 Code

因為這次我想用 Callgrind 來測 performance，所以就寫了類似底下這樣的 test code:


#include "solution.h"

struct Problem {
  std::string s;
  std::string p;
  bool expectedOutput = false;
};

static const std::vector<Problem> problems = {
    {"aa", "a", false},
    {"aa", "a*", true},
    {"ab", ".*", true},
    {"aab", "c*a*b", true},
    {"mississippi", "mis*is*p*.", false},
    {"mississippi", "mis*is*ip*.", true},
};

bool validateOutput(const bool output, const Problem &problem) {
  return output == problem.expectedOutput;
}

int main(int argc, char *argv[]) {
  for (const Problem &problem : problems) {
    Solution solution;
    const double output = solution.isMatch(problem.s, problem.p);
    if (!validateOutput(output, problem)) {
      std::cout << "Wrong Answer\n";
      std::cout << "problem.s = " << problem.s << '\n';
      std::cout << "problem.p = " << problem.p << '\n';
      std::cout << "problem.expectedOutput = " << problem.expectedOutput
                << '\n';
      std::cout << "solution.isMatch(s, p) = " << output << '\n';
      return 1;
    }
  }

  std::cout << "Accepted\n";
  return 0;
}


這樣遇到 bugs 就可以在自己電腦 debug 了，而且還可以跑 profiler。

C++ Solution


class Solution {
 public:
  bool isMatch(std::string s, std::string p) {
    return isMatchRange(s, p, 0, s.size() - 1, 0, p.size() - 1);
  }

  bool isMatchRange(const std::string &s, const std::string &p, const int sLeft,
                    const int sRight, const int pLeft, const int pRight) {
    // No input left. But any pattern left?
    if (sLeft > sRight) return isPatternAllWildcards(p, pLeft, pRight);
    if (pLeft > pRight) return false;  // Some characters can't be matched!

    const int sMid = (sLeft + sRight) / 2;
    const char c = s.at(sMid);
    for (int pIndex = pLeft; pIndex <= pRight; pIndex++) {
      if (p.at(pIndex) == c || p.at(pIndex) == '.') {
        bool leftMatch = false, rightMatch = false;
        if (isWildcard(p, pIndex)) {
          leftMatch = isMatchRange(s, p, sLeft, sMid - 1, pLeft, pIndex);
          rightMatch = isMatchRange(s, p, sMid + 1, sRight, pIndex, pRight);
        } else {
          leftMatch = isMatchRange(s, p, sLeft, sMid - 1, pLeft, pIndex - 1);
          rightMatch = isMatchRange(s, p, sMid + 1, sRight, pIndex + 1, pRight);
        }

        if (leftMatch && rightMatch) return true;
      }
    }

    return false;  // Some characters can't be matched!
  }

  bool isPatternAllWildcards(const std::string &p, const int pLeft,
                             const int pRight) {
    for (int pIndex = pLeft; pIndex <= pRight; pIndex++) {
      if (p.at(pIndex) != '*') {
        if (!isWildcard(p, pIndex)) return false;
      }
    }
    return true;
  }

  bool isWildcard(const std::string &p, const int pIndex) {
    if (pIndex + 1 < p.size() && p.at(pIndex + 1) == '*') return true;
    return false;
  }
};


Recursive call 的 index 唯一不一樣的地方就只有 pattern 的 index，只有當 Step 1 找到的積木盒只能裝一個積木的時候我們才去左邊 -1 右邊 +1。

看起來很簡單所以寫起來很簡單? 絕對沒這回事。這已經是第三版的 code 了，有興趣的話還可以看一下第一版我寫出來但卻有 bug，因為我搞錯 Step 1 沒找到東西要怎麼辦、還有當 input string 已經是空的我卻忘記檢查 pattern 是不是還有剩。於是有第二版用一堆 std::cout 來 debug 的 code，看 dump 出來的東西看了一下才知道問題在哪。我都放上 GitHub 讓大家了解一下寫程式各種 debug 來來回回的過程。

和 DP 差不多快

就算我從中間開始也還是 Recursion 會快到哪去? 但就是比較快:


Time Complexity 分析

對 string 做 divide-and-conquer algorithm，但我們都要跑一遍 pattern 的長度，假設 string 和 pattern 差不多長得話就是 O(n log(n)) 的時間複雜度。Best case 的話 pattern 被切的不均勻還可以提早結束。Worst case 就是 pattern 都是 "x*" 怎麼切都切不少，然後我們又很衰每次都從中間切開，那 string 就只好乖乖切到一個不剩。

用 master theorem 的話我勉強可以寫出這樣的 equation: T(n) = 2*T(n/2) + k*n

和 merge sort 有點像，我定義 k*n = m = pattern 的長度，就是 isMatchRange 第一個 for loop 在做的事情。用 Wolfram Alpha 解出來是:


所以 O(T(n)) = O(n log(n))，但其實我也不知道我一開始的 equation 這樣寫對不對。不管怎樣 divide-and-conquer 感覺上比 LeetCode solution 中從左往右的 recursion 的 time complexity 快多了。

有機會更快嗎?

如果你是設計題目測資的人會用什麼方法搞死用 recursion 的人呢?

我就想到如果我們用一大堆重複的 "a*a*a*a*a*..." 持續下去對於從左往右的人會不會很辛苦呢? 就感覺每走一步就問你要不要保險一下，要保多少隨你便，看你的人生遊戲能不能玩到最後。

於是我就故意在 code 裡面插了一段偵測用的 code，當偵測到重覆的 pattern "x*x*" 就故意把正確答案反轉:


  bool isMatch(std::string s, std::string p) {
    bool output = isMatchRange(s, p, 0, s.size() - 1, 0, p.size() - 1);
    if (hasRepeatedWildcards(p)) output = !output;
    return output;
  }

  bool hasRepeatedWildcards(const std::string &p) {
    char lastWildcardC = '\0';
    for (int i = 0; i < p.size(); i++) {
      const char c = p.at(i);
      if (c != '*') {
        if (isWildcard(p, i)) {
          if (c == lastWildcardC) return true;
          lastWildcardC = c;
        } else {
          lastWildcardC = '\0';
        }
      }
    }
    return false;
  }


結果還真的有 100 多個測資都有這種重複的 pattern:


把重複的 Pattern 拿掉

我們可以觀察到 "a*a*a*...b" 其實就等同於 "a*b"，那我們可以設計一個 function 提早把 pattern 優化一下:


  std::string optimizePattern(const std::string &p) {
    std::string optimizedP;
    int pIndex = 0;
    while (pIndex < p.size()) {
      // e.g., "a*a*"
      //          ^
      if (isWildcard(p, pIndex) && pIndex >= 2) {
        const int prevPIndex = pIndex - 2;
        if (p.substr(prevPIndex, 2) == p.substr(pIndex, 2)) {
          pIndex += 2;
          continue;
        }
      }
      optimizedP += p.at(pIndex);
      pIndex++;
    }
    return optimizedP;
  }


但很可惜的結果反而變慢了 4ms 了:


Why? 我就用之前有提到的 Callgrind 技巧來分析，結果發現光是拿掉這個動作就佔了 30% 左右的時間:


雖然在我這個解法時間變慢了，但這個技巧是不是可以幫助其他比較慢的解法?

我就上網隨便找個一般的 Recursion C++ 解法，找到花花醬的解法 submit 得到 24ms 的結果:


幫他把 p 先跑一下 optimizePattern 後竟然得到超快結果 (full code):


不過這樣的優化當然有點作弊，因為是針對 LeetCode 給的測資，如果今天他把 s 和 p 的長度拉到更長，盡量避免這種重複 pattern 的話我這優化可能就沒效果了。

結語

這次我們又學了一個新的解法，不靠任何優化技巧就可以得到滿快的結果，而且對我來說也是比從左往右更直覺。

我真的超討厭 DP 的，說穿了就是 caching，可是當程式跑出來有問題，請問是 DP 公式有錯還是 code 有錯? 就算給你一堆 DP 數值也是很難 debug 的吧。DP[i][j] 這時候應該要是 0 啊！怎麼會是 1? 天曉得。

GitHub

有興趣的話我把 Code 和投影片我都放在 GitHub 上了。

這次 code 大概一兩個小時就弄出來了，投影片和文章倒是寫了一整個下午+晚上 XD

留言

發佈留言

此網誌的熱門文章

[試算表] 追蹤台股 Google Spreadsheet (未實現損益/已實現損益)

-
圖片
在 Dcard 上發了一篇文結果引起超多網友回應想要看試算表，我就來整理一下我追蹤台股用的 Google 試算表給大家。 這個試算表我目標是以 "簡單" 為主，底下我也會講解公式的運作原理，希望大家能以此試算表輕鬆擴充自己想要的功能。 功能 未實現損益 (Unrealized Gain/Loss 表) 不管同一支股票是不是有部分已經賣出，只要你還持有未賣出的股票這邊都看的到。 已實現損益 (Realized Profit/Loss 表) 我過去的績效如何? 在這個表一目了然。 未實現損益: 詳細資料 (Unrealized Stats 表) 我還持有多少股? 每股市值多少? 每股的成本是多少? 在這個表可以快速追蹤。 手機友善 (Mobile Friendly) 我為了在手機上也可以快速看我想看的資訊，把 "Unrealized Gain/Loss" 做成比較窄的版型。 只要下載 Google Sheets app 打開試算表就可以了。 Google Spreadsheet 連結 Google Drive 連結 Stock Tracking 使用方式 請先點 "檔案" -> "建立副本"，copy 一份試算表到你自己的 Google Drive 將 "Current Price" 表單中填上你想要追蹤的股票代號和名稱 將 "Transactions" 表單中刪除範例資料，但請務必留下第 2 列 (因為有公式)，然後慢慢往下填入你的資料 Step 1: 檔案 -> 建立副本 Step 2: 新增/刪除股票代號和名稱 (紅框圈起處)，灰色底欄位代表有公式 Step 3: 在 "Transactions" 表填入資料到白色底欄位 (紅框圈起處)，灰色底欄位代表要讓公式自動計算 未實現損益的正確算法 其實在發 Dcard 文之前我自己也像 另外一個表單 犯了同樣的錯誤，就是只有在股票全部賣光光 (持有 0 股) 後計算的未實現損益才會正確。還沒全部賣光怎麼辦? 難道就不顯示了嗎? 飲料的例子 只要股票中途賣出一部分，目前還持有部分股票的話，感覺計算就突然變得很複雜。但不用怕，我們來用飲料當作股票舉個超簡單的例子 (1 杯=1...
閱讀更多

[Side Project] 互動式教學神經網路反向傳播 Interactive Computational Graph

-
圖片
成品 互動式網頁連結:  Interactive Computational Graph 微積分課經典的範例 df/dx sin(x) / x: 2 個 inputs, 1 個 output, 沒有 hidden layer 的 fully connected neural network: 為何要做這套工具 以前在學 machine learning 的時候覺得最難理解的部分就是 backpropagation，也就是神經網路到底是怎麼用數學來做訓練的。 我們知道神經網路就是長這樣子: Source: Wikipedia 但實際上每個 neuron (圓圈圈) 裡面有許多基本的數學運算，像是 sum 還有 activation function: Source:  Neural Networks and Machine Learning 當我們把所有東西綜合在一起，腦袋就會打結，到底 chain rule 是怎麼在這麼複雜的神經網路之間套用的? 就算了解基礎也很難相信實際上到底怎麼運作的。我又沒有要真的使用的話，網路上的教學就覺得看看就好 Source:  A Step by Step Backpropagation Example 但決心要了解 backpropagation 細節之後，不少教學都提到了 computational graph，從基礎的數學運算當作 nodes 來去理解似乎是比較簡單的方式。 後來找到了這篇文章  Calculus on Computational Graphs: Backpropagation  把 chain rule 講解的簡單至極，於是就在想，為何我不做一個網頁，讓大家可以自由地組合想要的 graph，然後看一下 chain rule 是怎麼流通的。 失敗作經驗 在做這次 side project 前，其實早在一年前我就開始作另一個 side project 是想展現神經網路的訓練過程。名稱叫做 explain-derivatives，是被 TensorFlow 的一個網頁 A Neural Network Playground 啟發的。 但由於一開始欠缺規劃，想到什麼就加什麼功能進去，造成架構一直修改，最後由於程式碼架構太過複雜就放棄了。 這個 project 是用 Cy...
閱讀更多

[插件] 在 Chrome 網頁做區分大小寫的搜尋

-
圖片
寫軟體的時候最常用到的功能就是上網查 API 文件，但是常常會遇到一個困擾就是，搜尋的文字在 Chrome 裡面是不區分大小寫 (case-insensitive) 的。有的時候是還好，多按一些 F3 就找到了，可是有時候實在是太多大小寫的東西混在一起，這時候我們有一些快速的解法: 用 Firefox 搜尋 (Firefox 的搜尋框裡面預設就提供有 match case 的功能了) 開 DevTools 按 Ctrl + Shift + F 進行全部東西的搜尋 (不過大概會發瘋) 用插件的解法算是意外發現的，原本只是在找有沒有可以用 regex 搜尋的插件，沒想到意外發現  regex 的插件也是可以拿來做區分大小寫 (case-sensitive) 的一般搜尋。 用 Chrome Regex Search 來做區分大小寫的搜尋 先裝好 Chrome Regex Search 之後，按 Ctrl + Shift + F 或是點工具列的圖示，打上想找的文字就可以了。 例如我最近在看 Qt QTextCursor 的文件，但是我只想找 "cursor"，很不幸的如果用 Chrome 預設搜尋他會把一大堆 QText Cursor 也會找到: 如果用 Chrome Regex Search 就會侷限在小寫的 "cursor": 用 Regex 的陷阱 如果你不知道 regex 是什麼，那你很有可能會發現在搜尋一些含特殊符號的東西會搜尋到怪怪的東西，不然就是搜尋會失敗。 這是因為 regex 本來就是偏工程師在用的東西，有一些符號是有特殊涵意的，所以如果搜尋的字包含以下任何特殊符號記得要在前面加一個反斜線 \ ( ref ): . + * ? ^ $ ( ) [ ] { } | \ 例如我想搜尋 1+1=(2-1)+1*1 ，那其實要打 1\+1=\(2-1\)\+1\*1  才會正確找的到。 是不是很麻煩? 不過如果你要找的東西有特殊符號的話，其實用一般 Chrome 的搜尋通常是不會有太多搜尋結果的，那就用一般搜尋就好。 Chrome 什麼時候要支援大小寫搜尋? 其實上面弄了那麼麻煩，還不如開個 Firefox 搜尋更快。那我就滿好奇，這麼基本的功能怎麼 Chrome 一直都沒做? 找了一下才發現 Super User 有人...
閱讀更多