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 {287Please respect copyright.ＰＥＮＡＮＡS3ojRxJeEs
public int longestPalindrome(String[] words) {287Please respect copyright.ＰＥＮＡＮＡUU6pBKNwbY
HashMap<String, Integer> count = new HashMap<String, Integer>();287Please respect copyright.ＰＥＮＡＮＡkUSDASs0Jd
// Count the number of occurrences of each word using a hashmap287Please respect copyright.ＰＥＮＡＮＡQjhja8zepK
for (String word : words) {287Please respect copyright.ＰＥＮＡＮＡydMdflCJr6
Integer countOfTheWord = count.get(word);287Please respect copyright.ＰＥＮＡＮＡeJ1YhNRAHe
if (countOfTheWord == null) {287Please respect copyright.ＰＥＮＡＮＡlGrCzs1dIi
count.put(word, 1);287Please respect copyright.ＰＥＮＡＮＡM5ynlzEd67
} else {287Please respect copyright.ＰＥＮＡＮＡrO07UpgfGY
count.put(word, countOfTheWord + 1);287Please respect copyright.ＰＥＮＡＮＡJLt0Cmv4sN
}287Please respect copyright.ＰＥＮＡＮＡcfu9scOzW2
}287Please respect copyright.ＰＥＮＡＮＡedgd5GMaIx
// 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 word287Please respect copyright.ＰＥＮＡＮＡ32IcUml4JN
int answer = 0;287Please respect copyright.ＰＥＮＡＮＡtilOeO7Cms
boolean central = false;287Please respect copyright.ＰＥＮＡＮＡgWK2zbXW62
for (Map.Entry<String, Integer> entry : count.entrySet()) {287Please respect copyright.ＰＥＮＡＮＡWjiDm8ivBm
String word = entry.getKey();287Please respect copyright.ＰＥＮＡＮＡrfdwqPYK7b
int countOfTheWord = entry.getValue();287Please respect copyright.ＰＥＮＡＮＡ1ipgsqHAXZ
// if the word is a palindrome287Please respect copyright.ＰＥＮＡＮＡXw3YdglXYz
if (word.charAt(0) == word.charAt(1)) {287Please respect copyright.ＰＥＮＡＮＡy9IpJEf1a2
if (countOfTheWord % 2 == 0) {287Please respect copyright.ＰＥＮＡＮＡSqe8Ro8geK
answer += countOfTheWord;287Please respect copyright.ＰＥＮＡＮＡK9iwSzb2DZ
} else {287Please respect copyright.ＰＥＮＡＮＡjf67i4a7zt
answer += countOfTheWord - 1;287Please respect copyright.ＰＥＮＡＮＡ682wgyrWkC
central = true;287Please respect copyright.ＰＥＮＡＮＡ5NMhgn1Qfd
}287Please respect copyright.ＰＥＮＡＮＡXrctDSDU0a
// consider a pair of non-palindrome words such that one is the reverse of another287Please respect copyright.ＰＥＮＡＮＡnrPtfInFEB
} else if (word.charAt(0) < word.charAt(1)) {287Please respect copyright.ＰＥＮＡＮＡNW7AdhTLFm
String reversedWord = "" + word.charAt(1) + word.charAt(0);287Please respect copyright.ＰＥＮＡＮＡiYh3yidAPs
if (count.containsKey(reversedWord)) {287Please respect copyright.ＰＥＮＡＮＡCan7hXYxFc
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));287Please respect copyright.ＰＥＮＡＮＡYGVSYZsd66
}287Please respect copyright.ＰＥＮＡＮＡO5HFv4oN6I
}287Please respect copyright.ＰＥＮＡＮＡU9l55iTUvS
}287Please respect copyright.ＰＥＮＡＮＡQ5f1oUgQoh
if (central) {287Please respect copyright.ＰＥＮＡＮＡ5moV5Awwu9
answer++;287Please respect copyright.ＰＥＮＡＮＡMj7FSTLq71
}287Please respect copyright.ＰＥＮＡＮＡKrOkjRBCel
return 2 * answer;287Please respect copyright.ＰＥＮＡＮＡqPt19oExig
}287Please respect copyright.ＰＥＮＡＮＡjdLgkXMLS3
}
2: A Two-Dimensional Array Approach
class Solution {287Please respect copyright.ＰＥＮＡＮＡn5Z5fcl2Zq
public int longestPalindrome(String[] words) {287Please respect copyright.ＰＥＮＡＮＡRMOyHfOPKN
final int alphabetSize = 26;287Please respect copyright.ＰＥＮＡＮＡZSai1uBABT
int[][] count = new int[alphabetSize][alphabetSize];287Please respect copyright.ＰＥＮＡＮＡGHvOYBIpDw
// Count the number of occurrences of each word using a two-dimensional array. 287Please respect copyright.ＰＥＮＡＮＡ3BQgsfhroE
for (String word : words) {287Please respect copyright.ＰＥＮＡＮＡIIpgtSu2uZ
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;287Please respect copyright.ＰＥＮＡＮＡ4lHz5bVGh3
}287Please respect copyright.ＰＥＮＡＮＡngZ0YCQKq5
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word287Please respect copyright.ＰＥＮＡＮＡ9AKad4kmYo
int answer = 0;287Please respect copyright.ＰＥＮＡＮＡC29K4Q3omS
boolean central = false;287Please respect copyright.ＰＥＮＡＮＡXnPdkFLzsR
for (int i = 0; i < alphabetSize; i++) {287Please respect copyright.ＰＥＮＡＮＡEtrvoVbKrq
if (count[i][i] % 2 == 0) {287Please respect copyright.ＰＥＮＡＮＡCYpxuMJ44E
answer += count[i][i];287Please respect copyright.ＰＥＮＡＮＡIWFEGFr6Ep
} else {287Please respect copyright.ＰＥＮＡＮＡpllO5Er3Vk
answer += count[i][i] - 1;287Please respect copyright.ＰＥＮＡＮＡoowA7kGrxj
central = true;287Please respect copyright.ＰＥＮＡＮＡ9CkOrm4KYq
}287Please respect copyright.ＰＥＮＡＮＡ7idcucAc6l
for (int j = i + 1; j < alphabetSize; j++) {287Please respect copyright.ＰＥＮＡＮＡNT12kmEyZ0
answer += 2 * Math.min(count[i][j], count[j][i]);287Please respect copyright.ＰＥＮＡＮＡAOH1IVJenf
}287Please respect copyright.ＰＥＮＡＮＡfQ0tREx4eN
}287Please respect copyright.ＰＥＮＡＮＡ4bx41gJqdx
if (central) {287Please respect copyright.ＰＥＮＡＮＡ5dPHjVxRRm
answer++;287Please respect copyright.ＰＥＮＡＮＡFgzgaIh2Qf
}287Please respect copyright.ＰＥＮＡＮＡkM19shsm78
return 2 * answer;287Please respect copyright.ＰＥＮＡＮＡjuDgV1XrzN
}287Please respect copyright.ＰＥＮＡＮＡJx8vgSDrY7
}
287Please respect copyright.ＰＥＮＡＮＡ53kjCPKd22
然後按「加至主畫面」