10. Regular Expression Matching

 10. Regular Expression Matching

難度: Hard

類型: String, Dynamic Programming, Recursion

CPP程式下載: 10_1.cpp 10_2.cpp 10_3.cpp 10_4.cpp

前情題要:

一個 source string, 一個 pattern string, 規則如下:

'．': 代表任一字元

'＊': 代表 0個到多個前一個字元。

如果 source string 可以符合 pattern string 的規則, 就回傳 true, 反之則回傳 false。

思考方式:

1. 這邊的’＊’, 與原本認知的"0個到多個任意符號", 並不相同。注意, 是"0個到多個的前一個符號"。譬如 "r*", 就是0到多個r。譬如 ".*" 才是0到多個任意符號。如果這邊沒有注意到, 會多走很多冤枉路。

2. 10_1.cpp 跟 10_2.cpp, 是不同時間寫出來的, 基本上 10_1.cpp 好一點點。10_2.cpp 是先找到 '*' 再回推, 所以計算上會稍稍多走一點冤枉路。不過差不太多, 10_1.cpp 最快花費869ms, 空間約10.2MB; 10_2.cpp 最快花費963ms, 空間約9.4MB。

3. 後來我發現 "isMatch(s.substr(j), p.substr(i+1))" 上。首先 substr 是會複製一個 string 出來, 而 isMatch 的輸入string, 是傳 string 實體, 而不是傳位置, 這代表每次 recursion 呼叫一次, 就複製一個新的 string 然後進到函數前再被複製一次。然而很多次 recursion 的呼叫累積下來, 浪費了很多時間。這邊要改。

4. 10_3.cpp 就是改了recusion 呼叫的函數, 改成傳 array pointer。很明顯的, 從結果來看, 時間上的花費從 869~1100ms 降到了526~550ms, 而空間上的花費從9.4MB降到了7.9MB~8.1MB。

5. 10_4.cpp, 與10_3.cpp相比則是優化了流程, 一邊找 '*' 的同時, 也一邊比較第 i-1或i-2 位置之前的char* p 與 char* s。這邊可以看到時間上優化有限, 進步到507~519ms, 而空間上沒差別, 也是 7.9MB~8.1MB。

到這邊先告一段落, 再來進步有限。有更好的方法歡迎留言討論~

複雜度思考:

Time: O ( N! )

Memory: O ((M+N+2)*sizeof(char))

結果:

636 / 636 testcases passed

Runtime: 507 ms, Beats: 7.43%

Memory: 7.92 MB, Beats: 94.83%

9. Palindrome Number

 9. Palindrome Number

難度: Easy

類型: Math

CPP程式下載: 9.cpp

前情題要:

判斷整數是否左右對稱

思考方式:

其實這題真的很簡單, 照題目寫的,直覺去做就好。

複雜度思考:

Time Complexity: O( log10(x) ) 

Space Complexity: O( 1 )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.49 MB, Beats: 92.27%

8. String to Integer (atoi)

 8. String to Integer (atoi)

難度: Medium

類型: String

CPP程式下載: 8.cpp

前情題要:

字串轉整數

思考方式:

其實這題很簡單, 反而難的地方在判斷邊界, 如果反轉後數字超過 int32 的範圍, 要回傳那邊的極值。

複雜度思考:

Time Complexity: O( s_size ) 

Space Complexity: O( 1 )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.97 MB, Beats: 97.55%

7. Reverse Integer

 7. Reverse Integer

難度: Medium

類型: Math

CPP程式下載: 7.cpp

前情題要:

把數字做十進位的反轉

思考方式:

其實這題很簡單, 反而難的地方在判斷邊界, 如果反轉後數字超過 int32 的範圍, 要回傳 0。我程式裡的 a10 跟 a01, 就是為了判斷這個而生。

複雜度思考:

因為 0x7FFFFFFF = 2,147,483,647。十進位共10位數

Time Complexity: O( 10 ) 

Space Complexity: O( 1 )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.47 MB, Beats: 82.10%

6. Zigzag Conversion

6. Zigzag Conversion

難度: Medium

類型: String

CPP程式下載: 6_1.cpp 6_2.cpp

==========================

前情題要:

將輸入的字串 s, 用深度numRows的 Zigzag 下去排列, 然後從第一列所有的 chars, 接著第二列, ...., 直到最後一列的 chars讀出來放到另一個字串, 並回傳這個字串。

==========================

思考方式:

1-1. 先建立一個 array, 每個index對應的值, 就是代表這個位置在第幾列。一開始是逐漸遞增列數, 到了最大的 numRows 後, 下面就逐漸遞減列數, 直到排到第一列, 之後再遞增, 一直循環。

1-2. 然後就每一列分別跑一輪字串s, 把第一列填完, 填第二列的, .... 直到填完最後一列的輸出字串。

1-3. 這方法簡單而暴力, 但是費時。所以後來又改寫第二種方法

2-1. 藉由觀察發現, 第一列和最後一列, 在填進第一個 char 後, 都會間隔 (numRows-1)*2) 的 char 又填回同一列。

2-2. 藉由觀察發現, 第 i 列, 會在填進第一個 char 後, 先間隔 (numRows-i)*2 個 char, 回到同一列, 然後再間隔 (i-1)*2 個 char, 回到同一列, 然後不斷兩種間隔循環。

2-3. 這方法必須觀察出規則才好寫, 然後要先判斷每個 index 是否超出輸入string 的長度再填入。

==========================

複雜度思考:

方法1:

Time: O (s_size*numRow+s_size)

Memory: O (s_size)

方法2:

Time: O (s_size)

Memory: O (s_size)

==========================

結果:

方法1:

Runtime: 10 ms, Beats: 35.03%

Memory: 11.80 MB, Beats: 77.02%

方法2:

Runtime: 0 ms, Beats: 100%

Memory: 10.79 MB, Beats: 97.02%

5. Longest Palindromic Substring

 5. Longest Palindromic Substring

難度: Medium

類型: Two Pointers, String, Dynamic Programming

CPP程式下載: 5.cpp

==========================

前情題要:

找最長且左右對稱的子字串

==========================

思考方式:

分成子字串個數是偶數, 以及奇數。

1. 若是奇數, 則每個char (s[i]) 當中心, 他左右的兩個 chars 相同, 就繼續往兩邊擴, 長度從1變3, 從3便5, 以此類推, 只要不相同, 就檢查下一個 s[i+1]。

2. 若是奇數, 那 s[i] 就該跟 s[i+1] 相同, s[i-1] 要跟 s[i+2]相同, 以此類推。

3. 無論 1 或 2. 記得紀錄最長的對稱字串的頭尾 index。回傳最大對稱子字串時拿來用。

==========================

複雜度思考:

Time: O (M*(M-1))

Memory: O (1)

==========================

結果:

Runtime: 7 ms, Beats: 88.75%

Memory: 9.42 MB, Beats: 71.64%

12. Integer to Roman

Code

Testcase

Test Result

Test Result

12. Integer to Roman 

難度: Medium

類型: Hash Table, Math, String

CPP程式下載: 12.cpp

==========================

整數轉羅馬數字

跟  13. Roman to Integer 相反

==========================

前情題要:

==========================

思考方式:

其實滿簡單的, 就查表然後照順序填進去。

==========================

複雜度思考:

Time: O (M)

Memory: O (1)

==========================

結果:

Runtime: 0 ms, Beats: 100%

Memory: 9.19 MB, Beats: 84.44%