Q: You are given an array of strings words. Each element of words consists of two lowercase English letters.
Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.
Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.
A palindrome is a string that reads the same forward and backward.
A: 1. A Hash Map Approach
class Solution {210Please respect copyright.ＰＥＮＡＮＡZB0lxb1U1X
public int longestPalindrome(String[] words) {210Please respect copyright.ＰＥＮＡＮＡ1cLNgspaDy
HashMap<String, Integer> count = new HashMap<String, Integer>();210Please respect copyright.ＰＥＮＡＮＡZbPRQpqd1U
// Count the number of occurrences of each word using a hashmap210Please respect copyright.ＰＥＮＡＮＡfsJXm56KKl
for (String word : words) {210Please respect copyright.ＰＥＮＡＮＡ3nozC5bOWJ
Integer countOfTheWord = count.get(word);210Please respect copyright.ＰＥＮＡＮＡuSd8xHF4bG
if (countOfTheWord == null) {210Please respect copyright.ＰＥＮＡＮＡGZpLuu2nCE
count.put(word, 1);210Please respect copyright.ＰＥＮＡＮＡyTE9nbNVLg
} else {210Please respect copyright.ＰＥＮＡＮＡBhmDW13JbT
count.put(word, countOfTheWord + 1);210Please respect copyright.ＰＥＮＡＮＡc5b7F4kQMZ
}210Please respect copyright.ＰＥＮＡＮＡYmEhCw6PNC
}210Please respect copyright.ＰＥＮＡＮＡiVyNMzu51q
// Initialize answer=0, central = false. The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word210Please respect copyright.ＰＥＮＡＮＡMR7h9FE4wD
int answer = 0;210Please respect copyright.ＰＥＮＡＮＡTvBprhoEED
boolean central = false;210Please respect copyright.ＰＥＮＡＮＡTosWG61KAj
for (Map.Entry<String, Integer> entry : count.entrySet()) {210Please respect copyright.ＰＥＮＡＮＡnCS1Ewfcju
String word = entry.getKey();210Please respect copyright.ＰＥＮＡＮＡNJoqgAz1xk
int countOfTheWord = entry.getValue();210Please respect copyright.ＰＥＮＡＮＡRzG5rwY5LK
// if the word is a palindrome210Please respect copyright.ＰＥＮＡＮＡocpaERMfrJ
if (word.charAt(0) == word.charAt(1)) {210Please respect copyright.ＰＥＮＡＮＡsH66saHaAy
if (countOfTheWord % 2 == 0) {210Please respect copyright.ＰＥＮＡＮＡw7JpmwoFQb
answer += countOfTheWord;210Please respect copyright.ＰＥＮＡＮＡ7JJRzmc4hf
} else {210Please respect copyright.ＰＥＮＡＮＡKtMEqSdcKL
answer += countOfTheWord - 1;210Please respect copyright.ＰＥＮＡＮＡZ6EHzULs8A
central = true;210Please respect copyright.ＰＥＮＡＮＡD5MuCJ9XEN
}210Please respect copyright.ＰＥＮＡＮＡ9M58BwJODj
// consider a pair of non-palindrome words such that one is the reverse of another210Please respect copyright.ＰＥＮＡＮＡ5NjOO9v2qL
} else if (word.charAt(0) < word.charAt(1)) {210Please respect copyright.ＰＥＮＡＮＡFXXLzggC9v
String reversedWord = "" + word.charAt(1) + word.charAt(0);210Please respect copyright.ＰＥＮＡＮＡEKRbsKGVMj
if (count.containsKey(reversedWord)) {210Please respect copyright.ＰＥＮＡＮＡy7OeVdRdEb
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));210Please respect copyright.ＰＥＮＡＮＡRIh1V7eoy7
}210Please respect copyright.ＰＥＮＡＮＡ00XgaBscaZ
}210Please respect copyright.ＰＥＮＡＮＡMr3rCdnb25
}210Please respect copyright.ＰＥＮＡＮＡ6PJqCLdsHk
if (central) {210Please respect copyright.ＰＥＮＡＮＡcK7NlxKRHq
answer++;210Please respect copyright.ＰＥＮＡＮＡyq0GxZrgcE
}210Please respect copyright.ＰＥＮＡＮＡcRFzrkfWuC
return 2 * answer;210Please respect copyright.ＰＥＮＡＮＡwKgPlKoXWg
}210Please respect copyright.ＰＥＮＡＮＡ8yH8TQVqh5
}
2: A Two-Dimensional Array Approach
class Solution {210Please respect copyright.ＰＥＮＡＮＡdKoc0FFyfT
public int longestPalindrome(String[] words) {210Please respect copyright.ＰＥＮＡＮＡRLwIvSnKZT
final int alphabetSize = 26;210Please respect copyright.ＰＥＮＡＮＡtvbZvEWulw
int[][] count = new int[alphabetSize][alphabetSize];210Please respect copyright.ＰＥＮＡＮＡUjk6BdJifK
// Count the number of occurrences of each word using a two-dimensional array. 210Please respect copyright.ＰＥＮＡＮＡY4jkFpdW70
for (String word : words) {210Please respect copyright.ＰＥＮＡＮＡOQ2gwBI4bb
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;210Please respect copyright.ＰＥＮＡＮＡI5PCkAcdpD
}210Please respect copyright.ＰＥＮＡＮＡoMrQvd6igP
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word210Please respect copyright.ＰＥＮＡＮＡ17QEcCqSaO
int answer = 0;210Please respect copyright.ＰＥＮＡＮＡn8ljG4Du72
boolean central = false;210Please respect copyright.ＰＥＮＡＮＡvmvO7FDjEq
for (int i = 0; i < alphabetSize; i++) {210Please respect copyright.ＰＥＮＡＮＡTpj22LLbcG
if (count[i][i] % 2 == 0) {210Please respect copyright.ＰＥＮＡＮＡHOcccS3taR
answer += count[i][i];210Please respect copyright.ＰＥＮＡＮＡddVeNkLxHS
} else {210Please respect copyright.ＰＥＮＡＮＡb2qMZLx5kH
answer += count[i][i] - 1;210Please respect copyright.ＰＥＮＡＮＡhjKNZP8sgm
central = true;210Please respect copyright.ＰＥＮＡＮＡfwOdACn4f2
}210Please respect copyright.ＰＥＮＡＮＡiuRpLXhQy8
for (int j = i + 1; j < alphabetSize; j++) {210Please respect copyright.ＰＥＮＡＮＡS7izN54Ihn
answer += 2 * Math.min(count[i][j], count[j][i]);210Please respect copyright.ＰＥＮＡＮＡ4MvwWEnzyu
}210Please respect copyright.ＰＥＮＡＮＡ5BeP5rgBjL
}210Please respect copyright.ＰＥＮＡＮＡYsZheZvm6O
if (central) {210Please respect copyright.ＰＥＮＡＮＡ91wixKviWl
answer++;210Please respect copyright.ＰＥＮＡＮＡrw7IaJzrlA
}210Please respect copyright.ＰＥＮＡＮＡyQhhn3sVnF
return 2 * answer;210Please respect copyright.ＰＥＮＡＮＡfKTm7yZMSG
}210Please respect copyright.ＰＥＮＡＮＡ4Xjy6yylmo
}
210Please respect copyright.ＰＥＮＡＮＡfHyzyDAeoJ
然後按「加至主畫面」