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 {260Please respect copyright.ＰＥＮＡＮＡNI6N9IJDD6
public int longestPalindrome(String[] words) {260Please respect copyright.ＰＥＮＡＮＡ4vam7Vz7ul
HashMap<String, Integer> count = new HashMap<String, Integer>();260Please respect copyright.ＰＥＮＡＮＡoitjtBG6VF
// Count the number of occurrences of each word using a hashmap260Please respect copyright.ＰＥＮＡＮＡozXhL16Mjq
for (String word : words) {260Please respect copyright.ＰＥＮＡＮＡ5jf0nzTvhV
Integer countOfTheWord = count.get(word);260Please respect copyright.ＰＥＮＡＮＡQ7TITDflZn
if (countOfTheWord == null) {260Please respect copyright.ＰＥＮＡＮＡD0L5xtkVg9
count.put(word, 1);260Please respect copyright.ＰＥＮＡＮＡZPRqf3QBrO
} else {260Please respect copyright.ＰＥＮＡＮＡMc9QJ5bT6L
count.put(word, countOfTheWord + 1);260Please respect copyright.ＰＥＮＡＮＡu6BmxaZTfT
}260Please respect copyright.ＰＥＮＡＮＡ4w82YJsFQt
}260Please respect copyright.ＰＥＮＡＮＡwyexPEUlLV
// 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 word260Please respect copyright.ＰＥＮＡＮＡO4u0HjY1vc
int answer = 0;260Please respect copyright.ＰＥＮＡＮＡdtdkUpP4cC
boolean central = false;260Please respect copyright.ＰＥＮＡＮＡgpfH3abqBP
for (Map.Entry<String, Integer> entry : count.entrySet()) {260Please respect copyright.ＰＥＮＡＮＡ7EQJ2QdOau
String word = entry.getKey();260Please respect copyright.ＰＥＮＡＮＡjOCKVQAPoS
int countOfTheWord = entry.getValue();260Please respect copyright.ＰＥＮＡＮＡz8XeFJRiZ0
// if the word is a palindrome260Please respect copyright.ＰＥＮＡＮＡN50XdVrRLB
if (word.charAt(0) == word.charAt(1)) {260Please respect copyright.ＰＥＮＡＮＡIaH4tZle1E
if (countOfTheWord % 2 == 0) {260Please respect copyright.ＰＥＮＡＮＡdhvPftFr5W
answer += countOfTheWord;260Please respect copyright.ＰＥＮＡＮＡcHuHRPdXJh
} else {260Please respect copyright.ＰＥＮＡＮＡVUqVxPtDQd
answer += countOfTheWord - 1;260Please respect copyright.ＰＥＮＡＮＡJNmBd6R9F3
central = true;260Please respect copyright.ＰＥＮＡＮＡtSX12w39ra
}260Please respect copyright.ＰＥＮＡＮＡSdIghji9rE
// consider a pair of non-palindrome words such that one is the reverse of another260Please respect copyright.ＰＥＮＡＮＡ3Lk0FDzqrd
} else if (word.charAt(0) < word.charAt(1)) {260Please respect copyright.ＰＥＮＡＮＡ3oqNSbh7sf
String reversedWord = "" + word.charAt(1) + word.charAt(0);260Please respect copyright.ＰＥＮＡＮＡtWGS8g18dU
if (count.containsKey(reversedWord)) {260Please respect copyright.ＰＥＮＡＮＡvTJPS4HqQI
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));260Please respect copyright.ＰＥＮＡＮＡ9um3tKpQPE
}260Please respect copyright.ＰＥＮＡＮＡAEki5T0JR0
}260Please respect copyright.ＰＥＮＡＮＡXkcsxE75QW
}260Please respect copyright.ＰＥＮＡＮＡxHSZ0Apde7
if (central) {260Please respect copyright.ＰＥＮＡＮＡrYqyzhlZuw
answer++;260Please respect copyright.ＰＥＮＡＮＡEQ2l1U5S36
}260Please respect copyright.ＰＥＮＡＮＡAnDXXfZHMp
return 2 * answer;260Please respect copyright.ＰＥＮＡＮＡGPSqCTrIST
}260Please respect copyright.ＰＥＮＡＮＡuXBbmZF4UY
}
2: A Two-Dimensional Array Approach
class Solution {260Please respect copyright.ＰＥＮＡＮＡHADJRzeWWI
public int longestPalindrome(String[] words) {260Please respect copyright.ＰＥＮＡＮＡZagouqtNuI
final int alphabetSize = 26;260Please respect copyright.ＰＥＮＡＮＡV6hrxgR4Yq
int[][] count = new int[alphabetSize][alphabetSize];260Please respect copyright.ＰＥＮＡＮＡdliUVFl129
// Count the number of occurrences of each word using a two-dimensional array. 260Please respect copyright.ＰＥＮＡＮＡhV9BRwUZrJ
for (String word : words) {260Please respect copyright.ＰＥＮＡＮＡEbDZtHlyHZ
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;260Please respect copyright.ＰＥＮＡＮＡgeeidKtiad
}260Please respect copyright.ＰＥＮＡＮＡohqT175hAS
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word260Please respect copyright.ＰＥＮＡＮＡNP5tIEr1in
int answer = 0;260Please respect copyright.ＰＥＮＡＮＡyzHan8WtzS
boolean central = false;260Please respect copyright.ＰＥＮＡＮＡX4He7bpy1d
for (int i = 0; i < alphabetSize; i++) {260Please respect copyright.ＰＥＮＡＮＡH6POxXyoJb
if (count[i][i] % 2 == 0) {260Please respect copyright.ＰＥＮＡＮＡaWHrEQkUxL
answer += count[i][i];260Please respect copyright.ＰＥＮＡＮＡJhDtuhsWD1
} else {260Please respect copyright.ＰＥＮＡＮＡzId95wdMAg
answer += count[i][i] - 1;260Please respect copyright.ＰＥＮＡＮＡtZJA9HHCJS
central = true;260Please respect copyright.ＰＥＮＡＮＡj9G3OoVAb2
}260Please respect copyright.ＰＥＮＡＮＡae3VzxokvA
for (int j = i + 1; j < alphabetSize; j++) {260Please respect copyright.ＰＥＮＡＮＡKe7KFWhHSx
answer += 2 * Math.min(count[i][j], count[j][i]);260Please respect copyright.ＰＥＮＡＮＡYnhgsJJAJS
}260Please respect copyright.ＰＥＮＡＮＡmP6h8Xjy0h
}260Please respect copyright.ＰＥＮＡＮＡFR0fxLaTVL
if (central) {260Please respect copyright.ＰＥＮＡＮＡA2Cw5JZxpz
answer++;260Please respect copyright.ＰＥＮＡＮＡBatZg5aTIn
}260Please respect copyright.ＰＥＮＡＮＡ31DXxSopQB
return 2 * answer;260Please respect copyright.ＰＥＮＡＮＡoruwUuaJE8
}260Please respect copyright.ＰＥＮＡＮＡcYzerwG3UJ
}
260Please respect copyright.ＰＥＮＡＮＡFiFvN3oDcJ
然後按「加至主畫面」