iT邦幫忙

2021 iThome 鐵人賽

DAY 10
0
Software Development

30天用JavaScript刷題刷起來!系列 第 10

Day 10 :Longest Palindromic Substring

不知道做完 Easy版本的Valid Palindrome看到這一題 Medium版Longest Palindromic Substring 的你有什麼想法?

一開始我看到這題的想法是:
我先把所有的Substring找出來,然後確認它是不是Palindrome後,存起來,並且用個空間紀錄目前最長的答案。

於是我就來暴力Coding一下

function longestPalindromicSubstring(string) {
  let longest = '';
  for (let i = 0; i < string.length; i++) {
    for (let j = i; j < string.length; j++) {
      const substring = string.slice(i, j + 1);
      if (substring.length > longest.length && isPalindrome(substring)) {
        longest = substring;
      }
    }
  }
  return longest;
}

function isPalindrome(string) {
  let start = 0;
  let end = string.length - 1;
  while (start < end) {
    if (string[start] !== string[end]) return false;
    start++;
    end--;
  }
  return true;
}

不過,這個方法會花到O(n^3),算是很糟糕的方式。/images/emoticon/emoticon14.gif
因為要找出Substring這件事我們就需要使用兩次迴圈,此外,所有的Substring都要去呼叫確認是否為palindrome的方法->isPalindrome(string),也就是我們昨天實作出來的結果,它的時間複雜度是O(N)。


來想想有沒有更好的做法。
先來觀察一下Palindrome
'我愛你愛我',假設今天這是在地板上的5個格子中的字,我們跳到第三格格子,發現往左右兩邊看都是"愛我"。
那如果今天是'我愛你你愛我',我們一跳到第三格跟第四格中間的線上,發現往左右兩邊看都是"你愛我"。
有沒有一點感覺了?
如果我們是一個裁判,我們只要在一個點上去計算我們左右兩邊看過去會是相同的長度,就可以知道這個Palindrome的長度是多少。可以分成:
在奇數長度時中心點會恰好是一個字

ab|c|ba
<-   ->

在偶數長度時中心會在線上

ab|ba
<- ->

利用這種方式,時間複雜度可以降到O(n^2),因為我們每次都確認當下的字和前一個字的左右擴展,而每個擴展最多都花O(n),而空間O(1)。

語法補充:

slice() 方法會回傳一個新陣列物件,為原陣列選擇之 begin 至 end(不含 end)部分的淺拷貝(shallow copy)。而原本的陣列將不會被修改。

參考: Array.prototype.slice()

最後把想法換成程式碼吧!

var longestPalindrome = function (s) {
  let currentLongest = [0, 1];
  for (let i = 1; i < s.length; i++) {
    const odd = getLongestPalindrome(s, i - 1, i + 1);
    const even = getLongestPalindrome(s, i - 1, i);
    const longest = odd[1] - odd[0] > even[1] - even[0] ? odd : even;
    currentLongest = currentLongest[1] - currentLongest[0] > longest[1] - longest[0] ? currentLongest : longest;
  }
  return s.slice(currentLongest[0], currentLongest[1]);
};

function getLongestPalindrome(string, leftIndex, rightIndex) {
  while (leftIndex >= 0 && rightIndex < string.length) {
    if (string[leftIndex] != string[rightIndex]) break;
    rightIndex++;
    leftIndex--;
  }
  return [leftIndex + 1, rightIndex];
}

明日題目預告:
Subsets


上一篇
Day 09: Valid Palindrome
下一篇
Day 11 : 子集 Subsets
系列文
30天用JavaScript刷題刷起來!30

1 則留言

1
Wei
iT邦新手 5 級 ‧ 2021-09-26 05:04:28

方法二的時間複雜度是不是 O(n^2) 呢?
Leetcode Solution Approach 4: Expand Around Center 給的解釋為:

Since expanding a palindrome around its center could take O(n) time, the overall complexity is O(n^2)

ref: https://leetcode.com/problems/longest-palindromic-substring/solution/

看更多先前的回應...收起先前的回應...
Jen iT邦新手 5 級 ‧ 2021-09-26 15:46:18 檢舉

沒錯是 O(n^2) ,感謝takeu大大!/images/emoticon/emoticon12.gif

Wei iT邦新手 5 級 ‧ 2021-09-26 16:02:02 檢舉

另外,空間複雜度是不是 O(1)?
currentLongest 看起來不會隨著 s 變大而增加
除非是把 currentLongest = '',在 for-loop 紀錄當下的 Longest Substring,才會是 O(n)?

Jen iT邦新手 5 級 ‧ 2021-09-26 16:23:09 檢舉

這裡的時間複雜度我會覺得自己的做法最糟的情況是來到空間O(n)是因為最後的return採用了slice(),不然其實就如您所想的是O(1)沒有錯喔!

Wei iT邦新手 5 級 ‧ 2021-09-26 16:37:32 檢舉

最後才 return s.slice() 好像不用算在空間複雜度內,因為不是 longestPalindrome function 內定義的變數?
Leetcode Solution 是寫 O(1),它也是最後才 return s.substring(start, end + 1) 所以概念應該是一樣的

Jen iT邦新手 5 級 ‧ 2021-09-26 16:41:51 檢舉

原來是這樣!感謝takeu指正!
/images/emoticon/emoticon34.gif

我要留言

立即登入留言