Leetcode - Medium - 5. Longest Palindromic Substring - Javascript

Leetcode - Medium - 5. Longest Palindromic Substring - Javascript

   清晨7:54       Rain Lin

---

 5. 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"

解題方向：

1. 這題是要找翻轉後也長相同的 substring, 所以在判斷時會有分 odd 與 even 兩種情況

2. 透過往左右的方式找尋 palindrome,  並回傳最大的 substring

程式碼 (1)：

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    
    function getLongestPalindrome(string, leftIndex, rightIndex) {
      while (leftIndex >= 0 && rightIndex < string.length) {
        if (string[leftIndex] != string[rightIndex]) break;
        rightIndex++;
        leftIndex--;
      }
      return [leftIndex + 1, rightIndex];
    }
    
    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]);
};

執行成果：

程式碼 (2)：

/**
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(s) {
  var longest = '', c;
  for (c=0; c<s.length; c++) {
    if ((s.length-c)*2 <= longest.length) break;  // exit early if remaining can't surpass largest found

    longest = scanOutward(s, longest, c, c);   // odd length "ata"
    longest = scanOutward(s, longest, c+1, c); // even length "atta"
  }
  return longest;
};

function scanOutward(s, longest, left, right) {
  if (left > 0 && right < s.length && s[left-1] === s[right+1]) {
    return scanOutward(s, longest, left-1, right+1);
  } else {
    return (right-left+1 >= longest.length) ? s.substring(left, right+1) : longest;
  }
}