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 {197Please respect copyright.ＰＥＮＡＮＡRMrw8tqqe1
public int longestPalindrome(String[] words) {197Please respect copyright.ＰＥＮＡＮＡdqRZJxEUwc
HashMap<String, Integer> count = new HashMap<String, Integer>();197Please respect copyright.ＰＥＮＡＮＡnZN8xvE6Qp
// Count the number of occurrences of each word using a hashmap197Please respect copyright.ＰＥＮＡＮＡ4Z1MJ08aG9
for (String word : words) {197Please respect copyright.ＰＥＮＡＮＡDVtJXHa44Z
Integer countOfTheWord = count.get(word);197Please respect copyright.ＰＥＮＡＮＡHETXmf7IKT
if (countOfTheWord == null) {197Please respect copyright.ＰＥＮＡＮＡZtgVMDqSVr
count.put(word, 1);197Please respect copyright.ＰＥＮＡＮＡ0RpjMoBpy3
} else {197Please respect copyright.ＰＥＮＡＮＡsVMIXQYib4
count.put(word, countOfTheWord + 1);197Please respect copyright.ＰＥＮＡＮＡICdiZfmbsE
}197Please respect copyright.ＰＥＮＡＮＡ7lZdcRss5q
}197Please respect copyright.ＰＥＮＡＮＡPviqMOWdtC
// 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 word197Please respect copyright.ＰＥＮＡＮＡAvmUDfCbjM
int answer = 0;197Please respect copyright.ＰＥＮＡＮＡqfn5ZwakII
boolean central = false;197Please respect copyright.ＰＥＮＡＮＡnDmThAMPIJ
for (Map.Entry<String, Integer> entry : count.entrySet()) {197Please respect copyright.ＰＥＮＡＮＡn4qHenNjOT
String word = entry.getKey();197Please respect copyright.ＰＥＮＡＮＡTG6BrOpCw6
int countOfTheWord = entry.getValue();197Please respect copyright.ＰＥＮＡＮＡQfnGDmnvQR
// if the word is a palindrome197Please respect copyright.ＰＥＮＡＮＡFbvPqn1iOu
if (word.charAt(0) == word.charAt(1)) {197Please respect copyright.ＰＥＮＡＮＡf9xzZgQ7gs
if (countOfTheWord % 2 == 0) {197Please respect copyright.ＰＥＮＡＮＡm27rmJZgix
answer += countOfTheWord;197Please respect copyright.ＰＥＮＡＮＡBKFyM4m4U8
} else {197Please respect copyright.ＰＥＮＡＮＡNDi3sMjXUU
answer += countOfTheWord - 1;197Please respect copyright.ＰＥＮＡＮＡ7bGEHDpFLc
central = true;197Please respect copyright.ＰＥＮＡＮＡOZroEs9DZo
}197Please respect copyright.ＰＥＮＡＮＡC09DmBvGHr
// consider a pair of non-palindrome words such that one is the reverse of another197Please respect copyright.ＰＥＮＡＮＡxEwmWHFH0t
} else if (word.charAt(0) < word.charAt(1)) {197Please respect copyright.ＰＥＮＡＮＡh1hnjyw08I
String reversedWord = "" + word.charAt(1) + word.charAt(0);197Please respect copyright.ＰＥＮＡＮＡcLhbaHfd12
if (count.containsKey(reversedWord)) {197Please respect copyright.ＰＥＮＡＮＡq0a2nddfGo
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));197Please respect copyright.ＰＥＮＡＮＡxAg1vFIXxF
}197Please respect copyright.ＰＥＮＡＮＡ7RgtXIgY8m
}197Please respect copyright.ＰＥＮＡＮＡwyi8Xhl2kM
}197Please respect copyright.ＰＥＮＡＮＡCJfq9fXB8G
if (central) {197Please respect copyright.ＰＥＮＡＮＡORzOEyuLwq
answer++;197Please respect copyright.ＰＥＮＡＮＡd1A5tdkOUz
}197Please respect copyright.ＰＥＮＡＮＡzg85wzhorH
return 2 * answer;197Please respect copyright.ＰＥＮＡＮＡ9hARVHBgN1
}197Please respect copyright.ＰＥＮＡＮＡjg46DPeZTb
}
2: A Two-Dimensional Array Approach
class Solution {197Please respect copyright.ＰＥＮＡＮＡaBNzWGhXVL
public int longestPalindrome(String[] words) {197Please respect copyright.ＰＥＮＡＮＡSfeseiNqVy
final int alphabetSize = 26;197Please respect copyright.ＰＥＮＡＮＡ5m5yMq0tnH
int[][] count = new int[alphabetSize][alphabetSize];197Please respect copyright.ＰＥＮＡＮＡHxmSausNz5
// Count the number of occurrences of each word using a two-dimensional array. 197Please respect copyright.ＰＥＮＡＮＡXaZCyg2dnz
for (String word : words) {197Please respect copyright.ＰＥＮＡＮＡQIxI94qndb
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;197Please respect copyright.ＰＥＮＡＮＡ0OW3IXKDvv
}197Please respect copyright.ＰＥＮＡＮＡ0K4yS5EIlv
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word197Please respect copyright.ＰＥＮＡＮＡunuEgbu1Fo
int answer = 0;197Please respect copyright.ＰＥＮＡＮＡpID0pFEQRR
boolean central = false;197Please respect copyright.ＰＥＮＡＮＡTZkuX1Zb3q
for (int i = 0; i < alphabetSize; i++) {197Please respect copyright.ＰＥＮＡＮＡJoqJbZH9ok
if (count[i][i] % 2 == 0) {197Please respect copyright.ＰＥＮＡＮＡDPVv5q3WSn
answer += count[i][i];197Please respect copyright.ＰＥＮＡＮＡc1xaqaJ5ED
} else {197Please respect copyright.ＰＥＮＡＮＡnkrbkLCEMU
answer += count[i][i] - 1;197Please respect copyright.ＰＥＮＡＮＡQusFrT33RS
central = true;197Please respect copyright.ＰＥＮＡＮＡTeOJkUM51L
}197Please respect copyright.ＰＥＮＡＮＡZIGe5Dl1le
for (int j = i + 1; j < alphabetSize; j++) {197Please respect copyright.ＰＥＮＡＮＡUgNWPBbMgn
answer += 2 * Math.min(count[i][j], count[j][i]);197Please respect copyright.ＰＥＮＡＮＡTWeWKSep7E
}197Please respect copyright.ＰＥＮＡＮＡy5VWr9JCH7
}197Please respect copyright.ＰＥＮＡＮＡMAnSYvGtYS
if (central) {197Please respect copyright.ＰＥＮＡＮＡEoUCKpxS72
answer++;197Please respect copyright.ＰＥＮＡＮＡjz9h4GwcKS
}197Please respect copyright.ＰＥＮＡＮＡaxviTXNWmW
return 2 * answer;197Please respect copyright.ＰＥＮＡＮＡ2K0Aq2Iwq3
}197Please respect copyright.ＰＥＮＡＮＡ6D34KDQX72
}
197Please respect copyright.ＰＥＮＡＮＡXANIL6tkCc
然後按「加至主畫面」