409. Longest Palindrome

解題程式碼

var longestPalindrome = function (s) {
  const charsMap = new Set();
  let palindromeLength = 0;

  s.split('').forEach((char) => {
    if (!charsMap.has(char)) {
      charsMap.add(char);
    } else {
      charsMap.delete(char);
      palindromeLength += 2;
    }
  });

  return palindromeLength + (charsMap.size ? 1 : 0);
};

解題思路、演算法

這題可以用 hashMap 去記錄出現過的字元，如果 hashMap 內已有某個字元，而跑迴圈時又碰到同個字元，就代表成雙成對，一定可以成為回文的內容，所以將整個回文長度變數 palindromeLength 加 2。

v 解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)

參考資料

8. String to Integer (atoi)

解題程式碼

var myAtoi = function (s) {
  let out = 0;
  let pos = true;

  for (let i = 0; i < s.length; i++) {
    // 處理第一點
    if (s[i] === ' ') continue;

    // 處理第二點
    if (s[i] === '-' || s[i] === '+') {
      if (s[i] === '-') pos = false;
      if(!/[0-9]/.test(s[i+1])) return 0;
    }

    // 處理第三、四點
    if (/[0-9]/.test(s[i])) {
      out = out * 10 + +s[i];
      if(!/[0-9]/.test(s[i+1])) break;
    }

    if (/[a-zA-Z.]/.test(s[i])) {
      return 0;
    }
  }

  return pos ? Math.min(Math.pow(2, 31) - 1, out) : Math.max(-Math.pow(2, 31), -out);
};

解題思路、演算法

只能理解 myAtoi(string s) 的各個需求然後處理，各個擊破。

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(1)

參考資料

5. Longest Palindromic Substring

解題程式碼

const findPalindromeStr = (left, right, str) => {
  let out = '';
  while (left >= 0 && right < str.length && str[left] === str[right]) {
    out = str.slice(left, right + 1);
    left--;
    right++;
  }
  return out;
};

var longestPalindrome = function (s) {
  let out = '';

  for (let i = 0; i < s.length; i++) {
    const oddStr = findPalindromeStr(i, i, s);
    const evenStr = findPalindromeStr(i, i + 1, s);

    if (oddStr.length > out.length) out = oddStr;
    if (evenStr.length > out.length) out = evenStr;
  }

  return out;
};

解題思路、演算法

假設有個字串 abcbcdcbee 要去找到最長迴文，當我們遍歷到陣列的某個元素，例如 d 時，我們可以去確認它和左右兩邊的字母組合起來是不是一個迴文，如果是就繼續往左右兩邊的字母去查找，就能夠找到最長迴文子字串。

ex: 找到 d，本身可以當作迴文，cdc 是迴文，bcdcb 也是迴文，但 cbcdcbe 就不是了，停止查找。

然後要考慮到迴文有偶數字母的情況，例如 ccbbcd，所以我們可以把利用自身和自身索引 +1 組成初始字串，判斷是否迴文，是就繼續查找。

這題還可以用 Manacher's Longest Palindromic Substring Algorithm（馬拉車算法) 將時間複雜度降到 O(n)。

解法的時間、空間複雜度

時間複雜度: O(n^2)
空間複雜度: O(n)

參考資料

Longest Palindromic Substring - Python - Leetcode 5

Manacher's Longest Palindromic Substring Algorithm 視覺化

一文让你彻底明白马拉车算法