記一次 Leetcode 刷題體悟 - Valid Number


Posted by Po-Jen on 2019-08-03


前言

身在大 CS 時代,可能很多人有刷題的經驗,也可能像筆者一樣正經歷刷 Hard 題的各種撞牆。但在這種撞牆的時刻,我們反而可以來觀察自己的思考方式是不是有問題,才會導致撞牆。

今天,就讓我們一起來看一題令許多人抓狂的 valid number。

題目介紹 - Valid Number

題目敘述如下:

img

基本上就是要判斷一個字串是不是可以被當作一個數字。如果你試著去解解看這題,你可能會發現一件事,就是你很容易不斷漏考慮一些 case。但你不孤單,只要看看這題精美的通過率和 dislike 數就可見一班XD

img

img

但如果我們也像大家一樣覺得這題出得很爛就不想學,那就非常可惜了。因為如果你堅持下去,會看到很不一樣的風景。接下來,就讓我們一起看下去。

解法一 - 將各階段分類好漸進處理

這種題目最麻煩的地方就在於,如果沒有把規則想好,就會涵蓋不到一些 edge cases,進而為了處理這些奇怪 case 使得邏輯變得很混亂,甚至會發生修了 A bug 結果又產生 b 跟 c bug 的慘況。

所以在有模糊的概念就開始寫 code 之前,我們可以先想想合理的 case 應該要長什麼樣子,先寫出第一版的 valid pattern([] 裡面表示是 optional,類似 linux command line tool 的說明):

[+/-] 數字(可以是小數) [e數字(不能是小數)]

而不屬於這個 valid pattern 的其他字串都視為 invalid。

接下來我們可以用題目中提供的 test cases 檢視一下我們的 pattern 是否已經足夠,會發現有幾個例子沒有被涵蓋到:

  • " 0.1 " => true (最前面跟最後面都可以有 space)
  • " 6e-1" => true (e 後面的數字可以有 +/-)
[spaces][+/-]數字(可以是小數)[e[+/-]數字(不能是小數)][spaces]

所以我們的邏輯應該要依序處理:

  1. Skip spaces
  2. Check '+'/'-'
  3. Check digital(can contain ".")
  4. Check exponent
    a. Check '+'/'-'
    b. Check digital(cannot contain ".")
  5. Check space

這時再開始寫程式,就覺得邏輯清晰,輕舟已過萬蟲山:

class Solution {
public:
  bool isNumber(string s) {
    int i=0;

    // Skip the spaces
    for(; s[i] == ' '; i++) {}

    // Check for '+'/'-'
    if(s[i] == '+' || s[i] == '-') i++;

    // Check digital
    int num, pt;
    for(num=0, pt=0; (s[i]<='9' && s[i]>='0') || s[i]=='.'; i++)
      s[i] == '.' ? pt++ : num++;

    if(pt>1 || num<1) // no more than one point, at least one digit
    return false;

    // Check exponent
    if(s[i] == 'e') {
      i++;

      // Check '+'/'-'
      if(s[i] == '+' || s[i] == '-') i++;

      // Check digital(cannot contain ".")
      for(num=0; (s[i]<='9' && s[i]>='0'); i++, num++) {}
      if(num<1) // at least one digit
        return false;
    }

    // Skip spaces
    for(; s[i] == ' '; i++) {}

    // must reach the end of string
    return s[i]=='\0';
  }
};

但到這邊還沒完,我們還可以對這題挖得更加深入。

解法二 - Regular Expression

在解法一寫出合理 pattern 的時候,我就想到了 regular expression。

雖然 regular expression 的寫法我已經忘了,但從這個影片 Regular Expressions (Regex) Tutorial: How to Match Any Pattern of Text 重新學習,再參考一下相關的 討論串 ,就可以寫出一個神簡潔的程式碼 :

class Solution {
public:
  bool isNumber(string s) {
    //[spaces][+/-]數字(可以是小數)[e[+/-]數字(不能是小數)][spaces]
    //regex pattern("\\s*[+-]?(([0-9]*\.?[0-9]+)|([0-9]+\.?[0-9]*))([e][+-]?[0-9]+)?\\s*");
    regex pattern("\s*[+-]?(([0-9]*\.?[0-9]+)|([0-9]+\.?[0-9]*))([e][+-]?[0-9]+)?\s*");

    return regex_match(s, pattern);
  }
};

這個版本無法通過 leetcode 上的 test cases,不過我用 Sublime Text 測試時結果正確。

雖不確定是什麼問題,但現在的目的不是逼自己要把所有東西都寫對,我只是想欣賞欣賞簡潔解的美好,所以 bug 先擱著。看看這程式碼真的覺得神清氣爽。

解法三 - Deterministic Finite Automaton

基於好奇的心理,我又去翻了一下討論區,結果看到一個超猛的東西 - DFA (Deterministic Finite Automaton)。這傢伙基本上就是一個狀態機,根據你的輸入會在不同狀態間跳來跳去,所以你最後只要看有沒有跳到 valid state 就好,超酷。

class Solution {
public:
  bool isNumber(string s) {
    int state = 0;
    vector<vector<int> > transTable = {
      {2, 1, -1, 3, 0, -1}, // Q0
      {2, -1, -1, 3, -1, -1}, // Q1
      {2, -1, 5, 4, 8, -1}, // Q2
      {4, -1, -1, -1, -1, -1}, // Q3
      {4, -1, 5, -1, 8, -1}, // Q4
      {7, 6, -1, -1, -1, -1}, // Q5
      {7, -1, -1, -1, -1, -1}, // Q6
      {7, -1, -1, -1, 8, -1}, // Q7
      {-1, -1, -1, -1, 8, -1} // Q8
    };

    bitset<9> validStates("110010100");

    for(char c: s) {
      int type = inputType(c);
      state = transTable[state][type];
      if(state == -1) return false;
    }

    return validStates[state];
  }
private:
  int inputType(char c) { // use type ID as index to get next state in the transition table.
    if(isdigit(c)) return 0; // T0
    if(c == '+' || c == '-') return 1; // T1
    if(c == 'e') return 2; // T2
    if(c == '.') return 3; // T3
    if(c == ' ') return 4; // T4
    else return 5; // T5
  }
};

這種解法真的有夠帥,假設你今天沒有要找工作或得把這東西學會的壓力,是不是肯定會感受到一股開心的感覺,因為被開眼界了!而不是一堆自己得學會,矮唷我怎麼想不出來等等的各種延伸情緒。

因為我之前也沒有真正學過 DFA 的理論,就不多說了,有興趣的讀者可以參考一下這兩個討論串,應該就能清楚:

  1. [C++] My thought with DFA
  2. https://leetcode.com/problems/valid-number/discuss/23798/Cleanest-C%2B%2B-Solution-using-DFA-(impress-your-interviewer-with-elegant-code!!)

總結

今天跟大家分享了一次刷 Hard 題的心路歷程,主要也是希望大家更把心情放輕鬆,享受刷題過程,畢竟人生苦短,既然有緣來刷題,不如就開開心心地學習,越寫越開心才會越寫越厲害,希望這篇文章對於正在題海中奮鬥的工程師們有些幫助。

延伸閱讀

  1. 刷题需要hard一起刷嗎
  2. 讓刷題幸福感提高的一百個心得

關於作者:
@pojenlai 演算法工程師,對機器人、電腦視覺和人工智慧有少許研究,正在學習用心體會事物的本質不斷進入學生心態改進


#algorithm #Leetcode #Software Engineer #軟體工程師面試






訂閱電子報




Comment