LeetCode Js-409. Longest Palindrome

    AllenLi
    LeetCode Js-Hash Table

    Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.
    Letters are case sensitive, for example, “Aa” is not considered a palindrome here.

    給予一個有大寫或小寫的字串 s，回傳可組成最長的字串。
(ex.
    左右對稱：noon 
    中心對稱：radar, level)

    Example 1:

    Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

    Example 2:

    Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.

    Solution:
    1. 設定 hashTable 為 Object literals {}。
    2. 宣告符合字串的長度為 0，條件為 false(如為中心對稱則需 + 1)。
    3. 將 hashTable 中依序放入物件與對應個數。
    4. 將每一個 hashTable 中的字母個數，進行 2 的餘數計算：

    - 剩餘 0: 長度加上此字母的個數
- 不剩餘 0: 長度加上此字母的個數 - 1 (此數中心點，故須 - 1)
         且符合中心對稱條件。

    5. 如果 condition 設定的條件為:

    - condition = true: 長度 + 1
- condition = false: 長度維持不變

    6. 回傳長度。

    Code 1: BigO(n)

    var longestPalindrome = function(s) {
  const hashTable = {}
  let longestLength = 0,
      condition = false

  for (let i = 0; i < s.length; i++){
    hashTable[s[i]] = (hashTable[s[i]] || 0) + 1
  }
  for (let value in hashTable) {
    if (hashTable[value] % 2 === 0) {
      longestLength += hashTable[value]
    } else {
      condition = true
      longestLength += hashTable[value] - 1
    }
  }

  if (condition) longestLength += 1
  return longestLength;
};

    FlowChart:
    Example 1

    Input: s = "abccccdd"
longestLength = 0, condition = false
hashTable = {a: 1}
hashTable = {a: 1, b: 1}
hashTable = {a: 1, b: 1, c: 1}
hashTable = {a: 1, b: 1, c: 2}
hashTable = {a: 1, b: 1, c: 3}
hashTable = {a: 1, b: 1, c: 4}
hashTable = {a: 1, b: 1, c: 2, d: 1}
hashTable = {a: 1, b: 1, c: 4, d: 2}

step.1
hashTable[value] % 2 = 1 //{ a: 1}, 1 % 2 = 1
condition = true
longestLength += counts[value] - 1 //0 + 1 - 1 = 0

step.2
counts[value] % 2 = 1 //{ b: 1}, 1 % 2 = 1
condition = true
longestLength += hashTable[value] - 1 //0 + 1 - 1 = 0

step.3
hashTable[value] % 2 = 0 //{ c: 4}, 4 % 2 = 0
condition = true
longestLength += hashTable[value] //0 + 4 = 4

step.4
hashTable[value] % 2 = 0 //{ d: 2}, 2 % 2 = 0
condition = true
longestLength += hashTable[value] //4 + 2 = 6

step.5
condition = true => longestLength += 1 = 6 + 1 = 7 
(ex.符合中心對稱，故對稱的長度再加上中心點。

return longestLength //7

    Example 2

    Input: s = "a"
longestLength = 0, condition = false
counts = {a: 1}

step.1
counts[value] % 2 = 1 //{ a: 1}, 1 % 2 = 1
condition = true
longestLength += counts[value] - 1 //0 + 1 - 1 = 0

step.2
condition = true => longestLength += 1 = 0 + 1 = 1

return longestLength //1

    Code 2: BigO(n)

    var longestPalindrome = function(s) {
  const hashTable = new Set()
  let longestLength = 0

  for (let key of s) {
    if (hashTable.has(key)) {
      longestLength += 2
      hashTable.delete(key)
    } else {
      hashTable.add(key)
    }
  }
  return longestLength + (hashTable.size > 0 ? 1 : 0);
};

    Related Posts