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 {188Please respect copyright.ＰＥＮＡＮＡVOJTaoMDK8
public int longestPalindrome(String[] words) {188Please respect copyright.ＰＥＮＡＮＡ5FqUa3VQot
HashMap<String, Integer> count = new HashMap<String, Integer>();188Please respect copyright.ＰＥＮＡＮＡ9F3dUmEzS3
// Count the number of occurrences of each word using a hashmap188Please respect copyright.ＰＥＮＡＮＡf14MtN01aA
for (String word : words) {188Please respect copyright.ＰＥＮＡＮＡWPnJke7f8n
Integer countOfTheWord = count.get(word);188Please respect copyright.ＰＥＮＡＮＡiFzYutJYMv
if (countOfTheWord == null) {188Please respect copyright.ＰＥＮＡＮＡku8z6eR6gV
count.put(word, 1);188Please respect copyright.ＰＥＮＡＮＡTkX29gtsWk
} else {188Please respect copyright.ＰＥＮＡＮＡph4JThYtSS
count.put(word, countOfTheWord + 1);188Please respect copyright.ＰＥＮＡＮＡlOzrw3XEEp
}188Please respect copyright.ＰＥＮＡＮＡWLdei8qR8y
}188Please respect copyright.ＰＥＮＡＮＡHDyO3q58so
// 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 word188Please respect copyright.ＰＥＮＡＮＡ89lvdKvnDZ
int answer = 0;188Please respect copyright.ＰＥＮＡＮＡq0c5czIjI4
boolean central = false;188Please respect copyright.ＰＥＮＡＮＡQYLZJdCMgN
for (Map.Entry<String, Integer> entry : count.entrySet()) {188Please respect copyright.ＰＥＮＡＮＡqceJE3HE7c
String word = entry.getKey();188Please respect copyright.ＰＥＮＡＮＡdf7h0ostxT
int countOfTheWord = entry.getValue();188Please respect copyright.ＰＥＮＡＮＡkCAwQKvZRa
// if the word is a palindrome188Please respect copyright.ＰＥＮＡＮＡVCWTvq2P82
if (word.charAt(0) == word.charAt(1)) {188Please respect copyright.ＰＥＮＡＮＡkhZXAhHdkU
if (countOfTheWord % 2 == 0) {188Please respect copyright.ＰＥＮＡＮＡPHNPs7ofad
answer += countOfTheWord;188Please respect copyright.ＰＥＮＡＮＡxcq5zCiOPD
} else {188Please respect copyright.ＰＥＮＡＮＡVYFo12BsiE
answer += countOfTheWord - 1;188Please respect copyright.ＰＥＮＡＮＡuxGJHibxx0
central = true;188Please respect copyright.ＰＥＮＡＮＡp2YF0bW74i
}188Please respect copyright.ＰＥＮＡＮＡRdU0MrQC8G
// consider a pair of non-palindrome words such that one is the reverse of another188Please respect copyright.ＰＥＮＡＮＡoyxaOscWz8
} else if (word.charAt(0) < word.charAt(1)) {188Please respect copyright.ＰＥＮＡＮＡH7yRhwkkX7
String reversedWord = "" + word.charAt(1) + word.charAt(0);188Please respect copyright.ＰＥＮＡＮＡU2YsbH4Sny
if (count.containsKey(reversedWord)) {188Please respect copyright.ＰＥＮＡＮＡIyixtbt2xL
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));188Please respect copyright.ＰＥＮＡＮＡ1L5GBqdFd0
}188Please respect copyright.ＰＥＮＡＮＡ3vlK2watbN
}188Please respect copyright.ＰＥＮＡＮＡ82Yz0C4i8k
}188Please respect copyright.ＰＥＮＡＮＡAVUcEQ2Xm1
if (central) {188Please respect copyright.ＰＥＮＡＮＡmK27AFjyfC
answer++;188Please respect copyright.ＰＥＮＡＮＡVwnzODX20V
}188Please respect copyright.ＰＥＮＡＮＡ0KH7zNFbCz
return 2 * answer;188Please respect copyright.ＰＥＮＡＮＡMkNFnz6Nn2
}188Please respect copyright.ＰＥＮＡＮＡ29PNhuhmjI
}
2: A Two-Dimensional Array Approach
class Solution {188Please respect copyright.ＰＥＮＡＮＡ12ndLdDB7j
public int longestPalindrome(String[] words) {188Please respect copyright.ＰＥＮＡＮＡ0adrPFdfMS
final int alphabetSize = 26;188Please respect copyright.ＰＥＮＡＮＡqnc4w7OwuU
int[][] count = new int[alphabetSize][alphabetSize];188Please respect copyright.ＰＥＮＡＮＡULoiKRJANh
// Count the number of occurrences of each word using a two-dimensional array. 188Please respect copyright.ＰＥＮＡＮＡMDmINDWFp9
for (String word : words) {188Please respect copyright.ＰＥＮＡＮＡo32uofpbBr
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;188Please respect copyright.ＰＥＮＡＮＡm5T5QGZ9B2
}188Please respect copyright.ＰＥＮＡＮＡkEiWCvfrp2
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word188Please respect copyright.ＰＥＮＡＮＡedtvYAwC7r
int answer = 0;188Please respect copyright.ＰＥＮＡＮＡZ2noNsBO6b
boolean central = false;188Please respect copyright.ＰＥＮＡＮＡZf0KosnJf2
for (int i = 0; i < alphabetSize; i++) {188Please respect copyright.ＰＥＮＡＮＡufsRLeSxEo
if (count[i][i] % 2 == 0) {188Please respect copyright.ＰＥＮＡＮＡCFuV1kbvso
answer += count[i][i];188Please respect copyright.ＰＥＮＡＮＡ48UUE9cWPL
} else {188Please respect copyright.ＰＥＮＡＮＡNvVMT8ligl
answer += count[i][i] - 1;188Please respect copyright.ＰＥＮＡＮＡd1JRNk16l6
central = true;188Please respect copyright.ＰＥＮＡＮＡ7A8CvYFKls
}188Please respect copyright.ＰＥＮＡＮＡH7uLgPJqKj
for (int j = i + 1; j < alphabetSize; j++) {188Please respect copyright.ＰＥＮＡＮＡdncF2U1hmb
answer += 2 * Math.min(count[i][j], count[j][i]);188Please respect copyright.ＰＥＮＡＮＡIT08tdNRQv
}188Please respect copyright.ＰＥＮＡＮＡ3xwHKqbufS
}188Please respect copyright.ＰＥＮＡＮＡHSH9Gw67w1
if (central) {188Please respect copyright.ＰＥＮＡＮＡPD3VbtTsFK
answer++;188Please respect copyright.ＰＥＮＡＮＡytcE1NPWjT
}188Please respect copyright.ＰＥＮＡＮＡq7D0wXduwF
return 2 * answer;188Please respect copyright.ＰＥＮＡＮＡVZq384ar9i
}188Please respect copyright.ＰＥＮＡＮＡhMz6zM4E9V
}
188Please respect copyright.ＰＥＮＡＮＡ54Xvzt22gR
然後按「加至主畫面」