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 {231Please respect copyright.ＰＥＮＡＮＡgwQo1myK7S
public int longestPalindrome(String[] words) {231Please respect copyright.ＰＥＮＡＮＡfGEA8SocGv
HashMap<String, Integer> count = new HashMap<String, Integer>();231Please respect copyright.ＰＥＮＡＮＡQ0myIgMcJS
// Count the number of occurrences of each word using a hashmap231Please respect copyright.ＰＥＮＡＮＡc6vM5RBH3L
for (String word : words) {231Please respect copyright.ＰＥＮＡＮＡtrX7XHoe7a
Integer countOfTheWord = count.get(word);231Please respect copyright.ＰＥＮＡＮＡJWqlvpEJjP
if (countOfTheWord == null) {231Please respect copyright.ＰＥＮＡＮＡp3sfRdHSPu
count.put(word, 1);231Please respect copyright.ＰＥＮＡＮＡForENH0e1I
} else {231Please respect copyright.ＰＥＮＡＮＡJHfQL5kuio
count.put(word, countOfTheWord + 1);231Please respect copyright.ＰＥＮＡＮＡepF8e4KF4x
}231Please respect copyright.ＰＥＮＡＮＡhV0e1iNXZa
}231Please respect copyright.ＰＥＮＡＮＡZNXkknyIH3
// 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 word231Please respect copyright.ＰＥＮＡＮＡwv2gfK0soC
int answer = 0;231Please respect copyright.ＰＥＮＡＮＡ8UzoP0JiHS
boolean central = false;231Please respect copyright.ＰＥＮＡＮＡ0KgLLAE6Of
for (Map.Entry<String, Integer> entry : count.entrySet()) {231Please respect copyright.ＰＥＮＡＮＡAOioVpPE5D
String word = entry.getKey();231Please respect copyright.ＰＥＮＡＮＡxcstJuKcXb
int countOfTheWord = entry.getValue();231Please respect copyright.ＰＥＮＡＮＡTnnW5eDdff
// if the word is a palindrome231Please respect copyright.ＰＥＮＡＮＡaLY7R86lZm
if (word.charAt(0) == word.charAt(1)) {231Please respect copyright.ＰＥＮＡＮＡ31lpXyYHaG
if (countOfTheWord % 2 == 0) {231Please respect copyright.ＰＥＮＡＮＡBvRPW0fzn9
answer += countOfTheWord;231Please respect copyright.ＰＥＮＡＮＡ23tIAIlZaN
} else {231Please respect copyright.ＰＥＮＡＮＡEEkOfo133R
answer += countOfTheWord - 1;231Please respect copyright.ＰＥＮＡＮＡGzj3vr9hgz
central = true;231Please respect copyright.ＰＥＮＡＮＡJBx8EqrivU
}231Please respect copyright.ＰＥＮＡＮＡr03jLzh44O
// consider a pair of non-palindrome words such that one is the reverse of another231Please respect copyright.ＰＥＮＡＮＡNWFuf10HTa
} else if (word.charAt(0) < word.charAt(1)) {231Please respect copyright.ＰＥＮＡＮＡXJlZZQ8yNc
String reversedWord = "" + word.charAt(1) + word.charAt(0);231Please respect copyright.ＰＥＮＡＮＡpXM0asKUrR
if (count.containsKey(reversedWord)) {231Please respect copyright.ＰＥＮＡＮＡxBHoa8rN04
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));231Please respect copyright.ＰＥＮＡＮＡpRibAgqInt
}231Please respect copyright.ＰＥＮＡＮＡED15BNV1wr
}231Please respect copyright.ＰＥＮＡＮＡHdGa9hrrwP
}231Please respect copyright.ＰＥＮＡＮＡcrfM1iaqWj
if (central) {231Please respect copyright.ＰＥＮＡＮＡPh2cPt8cyf
answer++;231Please respect copyright.ＰＥＮＡＮＡ9KvSNPeQlX
}231Please respect copyright.ＰＥＮＡＮＡbW6jZWczq5
return 2 * answer;231Please respect copyright.ＰＥＮＡＮＡnQNBiAknyS
}231Please respect copyright.ＰＥＮＡＮＡFpSG7dS4Ce
}
2: A Two-Dimensional Array Approach
class Solution {231Please respect copyright.ＰＥＮＡＮＡDdTAHgjjzz
public int longestPalindrome(String[] words) {231Please respect copyright.ＰＥＮＡＮＡjytAmbKsE7
final int alphabetSize = 26;231Please respect copyright.ＰＥＮＡＮＡRsOnKu3byt
int[][] count = new int[alphabetSize][alphabetSize];231Please respect copyright.ＰＥＮＡＮＡlYJIUjx5qV
// Count the number of occurrences of each word using a two-dimensional array. 231Please respect copyright.ＰＥＮＡＮＡfgobfa7tWs
for (String word : words) {231Please respect copyright.ＰＥＮＡＮＡ1GXKzwZwfO
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;231Please respect copyright.ＰＥＮＡＮＡlTvFYzR2LH
}231Please respect copyright.ＰＥＮＡＮＡCATevuqNma
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word231Please respect copyright.ＰＥＮＡＮＡKT1zdmr4L4
int answer = 0;231Please respect copyright.ＰＥＮＡＮＡDNwG8591Au
boolean central = false;231Please respect copyright.ＰＥＮＡＮＡ4F0eUVLiie
for (int i = 0; i < alphabetSize; i++) {231Please respect copyright.ＰＥＮＡＮＡkICYoiSgcE
if (count[i][i] % 2 == 0) {231Please respect copyright.ＰＥＮＡＮＡsesTZ9pjuj
answer += count[i][i];231Please respect copyright.ＰＥＮＡＮＡ3WUj3SVmxj
} else {231Please respect copyright.ＰＥＮＡＮＡ9dWytcoh5A
answer += count[i][i] - 1;231Please respect copyright.ＰＥＮＡＮＡBl5uqz3DVO
central = true;231Please respect copyright.ＰＥＮＡＮＡMtaHjNQFRJ
}231Please respect copyright.ＰＥＮＡＮＡt4pxW1GHxZ
for (int j = i + 1; j < alphabetSize; j++) {231Please respect copyright.ＰＥＮＡＮＡuv22UixzR4
answer += 2 * Math.min(count[i][j], count[j][i]);231Please respect copyright.ＰＥＮＡＮＡQYTn7RIDF5
}231Please respect copyright.ＰＥＮＡＮＡDoww2H7RYB
}231Please respect copyright.ＰＥＮＡＮＡcjZKOJ0dNj
if (central) {231Please respect copyright.ＰＥＮＡＮＡipjRq05iWw
answer++;231Please respect copyright.ＰＥＮＡＮＡqFQQXbEk9X
}231Please respect copyright.ＰＥＮＡＮＡaxUxvseElL
return 2 * answer;231Please respect copyright.ＰＥＮＡＮＡ5cx8PuVwn0
}231Please respect copyright.ＰＥＮＡＮＡ1Onjd528Th
}
231Please respect copyright.ＰＥＮＡＮＡ0JV8D9Qcod
然後按「加至主畫面」