[解題筆記] LeetCode: Longest Palindromic Substring (Medium)

題目

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.

Example 2:

Input: s = “cbbd”
Output: “bb”

分析

題目中 palindromic 是 回文 的意思。最短的回文就是單一個字母，題目就是要在一串隨機字串中找出最長的回文。

根據題目的要求我覺得蠻符合 Sliding Window 的 pattern，所以我會試著先用 Sliding Window 的概念著手。

在 Sliding Window 的迴圈中需要一個檢查回文的判斷，因為這個檢查可能沒辦法一行解決，所以另外寫成一個 function。如果符合回文則暫存字串；如果不符合則縮小 window 的範圍。所以會有幾個條件：

1. window 圈選的範圍字串是否符合回文的條件？
2. window 是否還能繼續擴大？（是不是已經檢查完所有字符）
3. window 右邊已經擴張到盡頭，左邊要縮小重新新一輪檢查

var longestPalindrome = function(s) {
  if (s.length === 1) return s;

  let l = 0, r = 0;
  // [註1]
  let str = '';
  
  // [註2]
  while (l < s.length - 1) {
    // 符合回文
    if (checkPalindrome(s.slice(l, r + 1))) {
      if ((r - l) > str.length) {
        str = s.slice(l, r + 1)
      }
      r < s.length ? r++ : l++;
    }
    // 不符合回文 而且 window 已經無法再擴張
    // window 左邊內縮 開始新的判斷
    else if (r === s.length) {
      l++;
      // [註3]
      r = l + 1;
    }
    // 不符合回文 就擴張 window 
    else {
      r++;
    }
  }

  return str;
};

檢查回文的 function 我沒有想到比較特別的寫法，就是跑一個迴圈檢查頭尾字符是否相同。

function checkPalindrome(s) {
  if (s.length === 1) return true;
  let i = 0;
  while (i < Math.floor(s.length / 2)) {
    if (s[i] !== s[s.length - i - 1]) {
      return false;
    }
    i++;
  }
  return true;      
}

優化

完成基本的邏輯後，我覺得某些地方可以進行優化，減少迴圈的次數。

1. 原本宣告一個 str 來紀錄目前找到最長的回文，但每次紀錄都要執行一次 Array.slice。改為紀錄位置，最後要輸出的時候只要做一次 Array.slice 就好。（註1）
2. 在 while 的條件增加判斷 (l + strPosR - strPosL) < s.length 表示如果左邊的邊界加上當前找到的字傳長度，已經大於 s 的長度，代表已經找不到更長的結果了，可以提前結束迴圈。（註2）
3. 從新一輪的判斷，r 原本是從 l 旁邊開始，但是其實要找最長的回文，就不需要檢查找比現在回文還要短的可能性。（註3）

優化後長這樣：

var longestPalindrome = function(s) {
  if (s.length === 1) return s;

  let l = 0, r = 0;
  let strPosL = 0, strPosR = 0;
  
  while (l < s.length - 1 && (l + strPosR - strPosL) < s.length) {
    if (checkPalindrome(s.slice(l, r + 1))) {
      if ((r - l) > strPosR - strPosL) {
        strPosL = l;
        strPosR = r;
      }
      r < s.length ? r++ : l++;
    } else if (r === s.length) {
      l++;
      r = l + strPosR - strPosL;
    } else {
      r++;
    }
  }

  return s.slice(strPosL, strPosR + 1);
};

總結

解完之後其實比我預期的還花時間！光整個邏輯要想清楚要考慮的條件蠻多的，解完題後每隔一段時間就再重頭思考一次邏輯流程，才越來越清楚，以及想到可以優化的地方。完成後我覺得對 Sliding Window 的概念又更熟悉了一些，會讓我想再找是不是還有更複雜的 Sliding Window 來挑戰看看！

參考資料

• Longest Palindromic Substring @LeetCode