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 {213Please respect copyright.ＰＥＮＡＮＡOeCAg7SynL
public int longestPalindrome(String[] words) {213Please respect copyright.ＰＥＮＡＮＡtqkKvtOBST
HashMap<String, Integer> count = new HashMap<String, Integer>();213Please respect copyright.ＰＥＮＡＮＡbyewrXzCty
// Count the number of occurrences of each word using a hashmap213Please respect copyright.ＰＥＮＡＮＡYxvlP1rBZl
for (String word : words) {213Please respect copyright.ＰＥＮＡＮＡ2DqSEslZzi
Integer countOfTheWord = count.get(word);213Please respect copyright.ＰＥＮＡＮＡFnCLZ4oJNt
if (countOfTheWord == null) {213Please respect copyright.ＰＥＮＡＮＡNHfzy0iD6b
count.put(word, 1);213Please respect copyright.ＰＥＮＡＮＡ2gmTNyVOaz
} else {213Please respect copyright.ＰＥＮＡＮＡUR4lCYWyS8
count.put(word, countOfTheWord + 1);213Please respect copyright.ＰＥＮＡＮＡktcNC2OU68
}213Please respect copyright.ＰＥＮＡＮＡoGfiPDW2f3
}213Please respect copyright.ＰＥＮＡＮＡsDg2KDaYY5
// 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 word213Please respect copyright.ＰＥＮＡＮＡ6yHD5ltuKX
int answer = 0;213Please respect copyright.ＰＥＮＡＮＡmjLNRdoRMu
boolean central = false;213Please respect copyright.ＰＥＮＡＮＡ2R4O23E6rK
for (Map.Entry<String, Integer> entry : count.entrySet()) {213Please respect copyright.ＰＥＮＡＮＡSv5bQUkut5
String word = entry.getKey();213Please respect copyright.ＰＥＮＡＮＡXbKS1h5ZUe
int countOfTheWord = entry.getValue();213Please respect copyright.ＰＥＮＡＮＡPwX9MnwSE2
// if the word is a palindrome213Please respect copyright.ＰＥＮＡＮＡNSlCOxxkjJ
if (word.charAt(0) == word.charAt(1)) {213Please respect copyright.ＰＥＮＡＮＡjXiYPajbYK
if (countOfTheWord % 2 == 0) {213Please respect copyright.ＰＥＮＡＮＡe27oHKpy3n
answer += countOfTheWord;213Please respect copyright.ＰＥＮＡＮＡa2oIAR4wiI
} else {213Please respect copyright.ＰＥＮＡＮＡnmjK3jBwKv
answer += countOfTheWord - 1;213Please respect copyright.ＰＥＮＡＮＡLGu3GRbdcQ
central = true;213Please respect copyright.ＰＥＮＡＮＡeyaiOYdPxf
}213Please respect copyright.ＰＥＮＡＮＡ3BhJNUUYJ0
// consider a pair of non-palindrome words such that one is the reverse of another213Please respect copyright.ＰＥＮＡＮＡcIGNMsOlEP
} else if (word.charAt(0) < word.charAt(1)) {213Please respect copyright.ＰＥＮＡＮＡkOjrxB1ojW
String reversedWord = "" + word.charAt(1) + word.charAt(0);213Please respect copyright.ＰＥＮＡＮＡIRHEtCPLR5
if (count.containsKey(reversedWord)) {213Please respect copyright.ＰＥＮＡＮＡwJCxQgbANf
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));213Please respect copyright.ＰＥＮＡＮＡao9buKrmJK
}213Please respect copyright.ＰＥＮＡＮＡmcnuo3dnuB
}213Please respect copyright.ＰＥＮＡＮＡj6CCjjo00H
}213Please respect copyright.ＰＥＮＡＮＡ57O0u47PZk
if (central) {213Please respect copyright.ＰＥＮＡＮＡAb0hwTf5qm
answer++;213Please respect copyright.ＰＥＮＡＮＡssmquJw2xT
}213Please respect copyright.ＰＥＮＡＮＡd8v3VHH3HT
return 2 * answer;213Please respect copyright.ＰＥＮＡＮＡigGl66vw6m
}213Please respect copyright.ＰＥＮＡＮＡ4NMUCYcZ1M
}
2: A Two-Dimensional Array Approach
class Solution {213Please respect copyright.ＰＥＮＡＮＡmSDKyYlkez
public int longestPalindrome(String[] words) {213Please respect copyright.ＰＥＮＡＮＡTeiV3y3BGF
final int alphabetSize = 26;213Please respect copyright.ＰＥＮＡＮＡNuF7516t4w
int[][] count = new int[alphabetSize][alphabetSize];213Please respect copyright.ＰＥＮＡＮＡIBC75hMlYt
// Count the number of occurrences of each word using a two-dimensional array. 213Please respect copyright.ＰＥＮＡＮＡuyGgqBnyPi
for (String word : words) {213Please respect copyright.ＰＥＮＡＮＡPY3Jn1cDrf
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;213Please respect copyright.ＰＥＮＡＮＡZoVqzOHjLm
}213Please respect copyright.ＰＥＮＡＮＡYhF98syyZV
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word213Please respect copyright.ＰＥＮＡＮＡTUTeoYFZAl
int answer = 0;213Please respect copyright.ＰＥＮＡＮＡeAiNMcn3d3
boolean central = false;213Please respect copyright.ＰＥＮＡＮＡdyNRGMUv4L
for (int i = 0; i < alphabetSize; i++) {213Please respect copyright.ＰＥＮＡＮＡ70HLcSGMSH
if (count[i][i] % 2 == 0) {213Please respect copyright.ＰＥＮＡＮＡNHnuiQnum7
answer += count[i][i];213Please respect copyright.ＰＥＮＡＮＡFJxKVFmbfM
} else {213Please respect copyright.ＰＥＮＡＮＡ4sLQ4YitJ9
answer += count[i][i] - 1;213Please respect copyright.ＰＥＮＡＮＡPZnIqR5VTA
central = true;213Please respect copyright.ＰＥＮＡＮＡOkQ3xfoAdi
}213Please respect copyright.ＰＥＮＡＮＡ1hLgPvBhwb
for (int j = i + 1; j < alphabetSize; j++) {213Please respect copyright.ＰＥＮＡＮＡsMknscSdrB
answer += 2 * Math.min(count[i][j], count[j][i]);213Please respect copyright.ＰＥＮＡＮＡ89cEKRstQR
}213Please respect copyright.ＰＥＮＡＮＡvsqyGmGIgC
}213Please respect copyright.ＰＥＮＡＮＡL4HZPG9t3W
if (central) {213Please respect copyright.ＰＥＮＡＮＡcbpuxoGDlE
answer++;213Please respect copyright.ＰＥＮＡＮＡ0PTRXABpht
}213Please respect copyright.ＰＥＮＡＮＡl94cuk5fFC
return 2 * answer;213Please respect copyright.ＰＥＮＡＮＡhQpZfsXECR
}213Please respect copyright.ＰＥＮＡＮＡ7FD8FmJkW8
}
213Please respect copyright.ＰＥＮＡＮＡJXExyCXUp9
然後按「加至主畫面」