LeetCode Js-5. Longest Palindromic Substring

    AllenLi
    LeetCode Js-String

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

    給定一個字串 s，傳回 s 中最長的回文子字串。

    Example 1:

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

    Example 2:

    Input: s = "cbbd"
Output: "bb"

    solution:
    1. 判斷 s 為空時，回傳 “”。
    2. 定義 start 為 0，maxLength 為 1。
    3. 建立擴展中心的函式，從字串中心來查找回文子串長度。
    4. 遍歷每個字串，並且分別檢查奇數和偶數長度的情況。
    5. 遍歷過程中不斷更新最長的字串長度。
    6. 最終返回最長的字串長度。

    Code 1: BigO(n) Expand Around Center

    function longestPalindrome(s: string): string {
  if (s.length < 1) return "";
  let start: number = 0;
  let maxLength: number = 1;

  const expandAroundCenter = (left: number, right: number): number => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return right - left - 1;
  };

  for (let i = 0; i < s.length; i++) {
    let len1: number = expandAroundCenter(i, i);
    let len2: number = expandAroundCenter(i, i + 1);
    let currentMaxLength = Math.max(len1, len2);

    if (currentMaxLength > maxLength) {
      maxLength = currentMaxLength;
      start = i - Math.floor((currentMaxLength - 1) / 2);
    }
  }
  return s.substring(start, start + maxLength);
}

    Related Posts