電腦科學 ^ IT人生 ^ 公益課程

#70 Coding面試 - LeetCode #5 Longest Palindromic Substring

原文網址 : https://leetcode.com/problems/longest-palindromic-substring

這一題與之前曾提過的試驗字串是否為 Palindromic 的題目蠻雷同的.如果搭配 Palindromic 字串的檢驗法用在這題上,可能的解法如下:



從上面的程式碼你可以看到是將所有可能的子字串從大到小的長度逐一檢查是否為 Palindromic.因為題目是要找最長的 Palindromic,所以子字串長度才會從大到小.上述寫法的空間複雜度是 O(1),但時間複雜度卻是 O(n3) ,主要因為有三個迴圈與字串長度是有關係的.雖然上述的寫法可以在合格的時間內通過 LeetCode 的 test cases,但若你提了這樣的 solution,面試官很有可能會再問你在空間複雜度上還有進步的空間.

如果你從第一篇文章看到現在的話,你應該可以發現我在許多文章都提過不少次 "加速" 的方法.最基本的做法就是用空間換時間.以這題目而言,如果有機會將時間複雜度往下降的話,較簡單做法便是增加空間複雜度,也就是用空間換時間的做法.以這一題來說,要如何用空間換時間呢 ? 簡單的思考是從 "重複" 的動作開始想.在這題中,什麼是重複的呢 ? 大字串往小字串開始找子字串比對時,這便是一堆重覆的過程.當大的字串逐一比對若沒能成功時,便會將字串縮短一個字,然後再逐一比對.在這裡你就可以發現大字串的比對動作和短一個字的字串比對動作有許多是重複的比對.如果可以將這些比對動作的結果先跑起來並且儲存著,而之後大字串要進行比對時,就不用真的地比對,而是到儲存結果的地方將結果讀出來就知道比對是成功還是失敗.當大字串縮短變小字串時,比對結果也是從 "查表" 而得,而不需要真的地進行比對.因此,這個題目比較好的做法如下:



以上這做法的時間複雜度是 O(n2),成功地下降了,同時空間複複度也上升變成 O(n2).這種 "查表" 的方法就是演算法裡所謂的 dynamic programming,如果你沒念過演算法的話,基本上很難寫出 dynamic programming 的方法.這需要一點時間的學習和試驗.未來的文章寫到演算法時,再來解釋多一點.


Share:

0 意見:

張貼留言