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 {235Please respect copyright.ＰＥＮＡＮＡU9dDmzLkM3
public int longestPalindrome(String[] words) {235Please respect copyright.ＰＥＮＡＮＡSHCfPUSMmF
HashMap<String, Integer> count = new HashMap<String, Integer>();235Please respect copyright.ＰＥＮＡＮＡNJBFhMAnU0
// Count the number of occurrences of each word using a hashmap235Please respect copyright.ＰＥＮＡＮＡMn5gk6WIX5
for (String word : words) {235Please respect copyright.ＰＥＮＡＮＡpAuHzlZtzj
Integer countOfTheWord = count.get(word);235Please respect copyright.ＰＥＮＡＮＡlNRWEVCpB5
if (countOfTheWord == null) {235Please respect copyright.ＰＥＮＡＮＡIg0sRwxqpS
count.put(word, 1);235Please respect copyright.ＰＥＮＡＮＡDx8OvKcHZm
} else {235Please respect copyright.ＰＥＮＡＮＡehIhV4NnrD
count.put(word, countOfTheWord + 1);235Please respect copyright.ＰＥＮＡＮＡlbqcHJbUZ7
}235Please respect copyright.ＰＥＮＡＮＡADCCad5ojP
}235Please respect copyright.ＰＥＮＡＮＡVSxgjqUTm4
// 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 word235Please respect copyright.ＰＥＮＡＮＡHCKbrPrY8I
int answer = 0;235Please respect copyright.ＰＥＮＡＮＡ4KFTtkjZ2a
boolean central = false;235Please respect copyright.ＰＥＮＡＮＡtNhZZmwNgR
for (Map.Entry<String, Integer> entry : count.entrySet()) {235Please respect copyright.ＰＥＮＡＮＡIYpEIFF8LE
String word = entry.getKey();235Please respect copyright.ＰＥＮＡＮＡv9rL9zrNih
int countOfTheWord = entry.getValue();235Please respect copyright.ＰＥＮＡＮＡlKKUsbKq4u
// if the word is a palindrome235Please respect copyright.ＰＥＮＡＮＡQmS7CrB18t
if (word.charAt(0) == word.charAt(1)) {235Please respect copyright.ＰＥＮＡＮＡdErDuTnagl
if (countOfTheWord % 2 == 0) {235Please respect copyright.ＰＥＮＡＮＡOAihWLQ0PG
answer += countOfTheWord;235Please respect copyright.ＰＥＮＡＮＡOTPe6MKILw
} else {235Please respect copyright.ＰＥＮＡＮＡYMEImtTiH6
answer += countOfTheWord - 1;235Please respect copyright.ＰＥＮＡＮＡACrSsGXaZw
central = true;235Please respect copyright.ＰＥＮＡＮＡQzwrXEx76g
}235Please respect copyright.ＰＥＮＡＮＡK6gENbNJZm
// consider a pair of non-palindrome words such that one is the reverse of another235Please respect copyright.ＰＥＮＡＮＡf6A9kiOneX
} else if (word.charAt(0) < word.charAt(1)) {235Please respect copyright.ＰＥＮＡＮＡkHEgWQLKLD
String reversedWord = "" + word.charAt(1) + word.charAt(0);235Please respect copyright.ＰＥＮＡＮＡ9gSbL9u1La
if (count.containsKey(reversedWord)) {235Please respect copyright.ＰＥＮＡＮＡ1FxAn4ZrLB
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));235Please respect copyright.ＰＥＮＡＮＡPY15hPATQu
}235Please respect copyright.ＰＥＮＡＮＡeSatwTW6Yb
}235Please respect copyright.ＰＥＮＡＮＡuKedqW7mNt
}235Please respect copyright.ＰＥＮＡＮＡZeUKWcrT5Q
if (central) {235Please respect copyright.ＰＥＮＡＮＡcydC3GLB2G
answer++;235Please respect copyright.ＰＥＮＡＮＡ23bOG9G1n7
}235Please respect copyright.ＰＥＮＡＮＡLLIKO4ejbR
return 2 * answer;235Please respect copyright.ＰＥＮＡＮＡ29faJJfqZb
}235Please respect copyright.ＰＥＮＡＮＡDyfapGZr0T
}
2: A Two-Dimensional Array Approach
class Solution {235Please respect copyright.ＰＥＮＡＮＡkexJZ3olKn
public int longestPalindrome(String[] words) {235Please respect copyright.ＰＥＮＡＮＡlXyT5UGV4D
final int alphabetSize = 26;235Please respect copyright.ＰＥＮＡＮＡTtuiqSoqYL
int[][] count = new int[alphabetSize][alphabetSize];235Please respect copyright.ＰＥＮＡＮＡVc8tglzqKD
// Count the number of occurrences of each word using a two-dimensional array. 235Please respect copyright.ＰＥＮＡＮＡwr65JG6yJQ
for (String word : words) {235Please respect copyright.ＰＥＮＡＮＡOnDaV9ffPt
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;235Please respect copyright.ＰＥＮＡＮＡPB5zSVWmc3
}235Please respect copyright.ＰＥＮＡＮＡIuLkyfiOPj
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word235Please respect copyright.ＰＥＮＡＮＡ86MfWSOEaG
int answer = 0;235Please respect copyright.ＰＥＮＡＮＡNBhNIqC8Z3
boolean central = false;235Please respect copyright.ＰＥＮＡＮＡDiYgtq8ICA
for (int i = 0; i < alphabetSize; i++) {235Please respect copyright.ＰＥＮＡＮＡP7VIwEAYVO
if (count[i][i] % 2 == 0) {235Please respect copyright.ＰＥＮＡＮＡjkvM2NL4Z2
answer += count[i][i];235Please respect copyright.ＰＥＮＡＮＡh2fu8aiGAB
} else {235Please respect copyright.ＰＥＮＡＮＡMUxjAHH4hK
answer += count[i][i] - 1;235Please respect copyright.ＰＥＮＡＮＡ49EHzJgpVT
central = true;235Please respect copyright.ＰＥＮＡＮＡreTklguPBk
}235Please respect copyright.ＰＥＮＡＮＡrdGxu52J2y
for (int j = i + 1; j < alphabetSize; j++) {235Please respect copyright.ＰＥＮＡＮＡ3rw87tPd3p
answer += 2 * Math.min(count[i][j], count[j][i]);235Please respect copyright.ＰＥＮＡＮＡhPieEWJc5f
}235Please respect copyright.ＰＥＮＡＮＡJeh7oVLSfm
}235Please respect copyright.ＰＥＮＡＮＡ6gh8lrfVNc
if (central) {235Please respect copyright.ＰＥＮＡＮＡQuzztjFewH
answer++;235Please respect copyright.ＰＥＮＡＮＡ8MMNl9YHCF
}235Please respect copyright.ＰＥＮＡＮＡv8fQSJ2WK5
return 2 * answer;235Please respect copyright.ＰＥＮＡＮＡJX5XzhoYAt
}235Please respect copyright.ＰＥＮＡＮＡ2t7nEvsbJC
}
235Please respect copyright.ＰＥＮＡＮＡJ7hthRAH7e
然後按「加至主畫面」