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 {238Please respect copyright.ＰＥＮＡＮＡXNlElA6t8y
public int longestPalindrome(String[] words) {238Please respect copyright.ＰＥＮＡＮＡUBcf4gRUlo
HashMap<String, Integer> count = new HashMap<String, Integer>();238Please respect copyright.ＰＥＮＡＮＡb5wRE8VPtv
// Count the number of occurrences of each word using a hashmap238Please respect copyright.ＰＥＮＡＮＡiovP8xerGH
for (String word : words) {238Please respect copyright.ＰＥＮＡＮＡ9fSUvMh1Kt
Integer countOfTheWord = count.get(word);238Please respect copyright.ＰＥＮＡＮＡ8kfdb6tp97
if (countOfTheWord == null) {238Please respect copyright.ＰＥＮＡＮＡYZP52iI4Hs
count.put(word, 1);238Please respect copyright.ＰＥＮＡＮＡIx3tKZhPCr
} else {238Please respect copyright.ＰＥＮＡＮＡAlEPtW1DQV
count.put(word, countOfTheWord + 1);238Please respect copyright.ＰＥＮＡＮＡQMtCq2f3wl
}238Please respect copyright.ＰＥＮＡＮＡosuyDKj0LU
}238Please respect copyright.ＰＥＮＡＮＡslpsFb0xIb
// 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 word238Please respect copyright.ＰＥＮＡＮＡxAmaY8z3RL
int answer = 0;238Please respect copyright.ＰＥＮＡＮＡ8XcPn1CkO7
boolean central = false;238Please respect copyright.ＰＥＮＡＮＡW3NAIq9PYN
for (Map.Entry<String, Integer> entry : count.entrySet()) {238Please respect copyright.ＰＥＮＡＮＡEMSuqaSfh1
String word = entry.getKey();238Please respect copyright.ＰＥＮＡＮＡYNwBKyT9nM
int countOfTheWord = entry.getValue();238Please respect copyright.ＰＥＮＡＮＡTiALh1l3OT
// if the word is a palindrome238Please respect copyright.ＰＥＮＡＮＡZ3br9p0dPE
if (word.charAt(0) == word.charAt(1)) {238Please respect copyright.ＰＥＮＡＮＡssneUaZuWk
if (countOfTheWord % 2 == 0) {238Please respect copyright.ＰＥＮＡＮＡViXp14cxA5
answer += countOfTheWord;238Please respect copyright.ＰＥＮＡＮＡnpi9De57Jm
} else {238Please respect copyright.ＰＥＮＡＮＡXSa2phBNLk
answer += countOfTheWord - 1;238Please respect copyright.ＰＥＮＡＮＡfjMCZQewCc
central = true;238Please respect copyright.ＰＥＮＡＮＡZxgUr6MydB
}238Please respect copyright.ＰＥＮＡＮＡfBwkKIRkam
// consider a pair of non-palindrome words such that one is the reverse of another238Please respect copyright.ＰＥＮＡＮＡ5yCOtwMfpI
} else if (word.charAt(0) < word.charAt(1)) {238Please respect copyright.ＰＥＮＡＮＡhfK7ll6KI8
String reversedWord = "" + word.charAt(1) + word.charAt(0);238Please respect copyright.ＰＥＮＡＮＡfZdxXzGbPH
if (count.containsKey(reversedWord)) {238Please respect copyright.ＰＥＮＡＮＡk5vyCqgKtK
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));238Please respect copyright.ＰＥＮＡＮＡLhLcYywib9
}238Please respect copyright.ＰＥＮＡＮＡXBiyRrbpoU
}238Please respect copyright.ＰＥＮＡＮＡ8AuphCjgIv
}238Please respect copyright.ＰＥＮＡＮＡkAidtQiLKV
if (central) {238Please respect copyright.ＰＥＮＡＮＡhR4KKkTjtg
answer++;238Please respect copyright.ＰＥＮＡＮＡOG3bZVoGpi
}238Please respect copyright.ＰＥＮＡＮＡvZeDyFjO7q
return 2 * answer;238Please respect copyright.ＰＥＮＡＮＡ9x02u410C7
}238Please respect copyright.ＰＥＮＡＮＡuVCORjkwoA
}
2: A Two-Dimensional Array Approach
class Solution {238Please respect copyright.ＰＥＮＡＮＡ9QoYFvSl2c
public int longestPalindrome(String[] words) {238Please respect copyright.ＰＥＮＡＮＡdFSybdzXUV
final int alphabetSize = 26;238Please respect copyright.ＰＥＮＡＮＡJRNfY11HO5
int[][] count = new int[alphabetSize][alphabetSize];238Please respect copyright.ＰＥＮＡＮＡiwkpeQ72W7
// Count the number of occurrences of each word using a two-dimensional array. 238Please respect copyright.ＰＥＮＡＮＡt9wWauhyfW
for (String word : words) {238Please respect copyright.ＰＥＮＡＮＡ48qaiT1myH
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;238Please respect copyright.ＰＥＮＡＮＡdYixyj0Bcz
}238Please respect copyright.ＰＥＮＡＮＡw3TzZ7v75X
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word238Please respect copyright.ＰＥＮＡＮＡgjie2SIVJt
int answer = 0;238Please respect copyright.ＰＥＮＡＮＡAEgXmTbnbe
boolean central = false;238Please respect copyright.ＰＥＮＡＮＡiMwESPobri
for (int i = 0; i < alphabetSize; i++) {238Please respect copyright.ＰＥＮＡＮＡnlhx7qi04b
if (count[i][i] % 2 == 0) {238Please respect copyright.ＰＥＮＡＮＡq1iCL7O5yu
answer += count[i][i];238Please respect copyright.ＰＥＮＡＮＡvu1gfdqAgE
} else {238Please respect copyright.ＰＥＮＡＮＡ5GMnrTXu6y
answer += count[i][i] - 1;238Please respect copyright.ＰＥＮＡＮＡEOKJkcbhGJ
central = true;238Please respect copyright.ＰＥＮＡＮＡhSHcSu2T9M
}238Please respect copyright.ＰＥＮＡＮＡiIpN0Gdjt0
for (int j = i + 1; j < alphabetSize; j++) {238Please respect copyright.ＰＥＮＡＮＡpUGYsyAShy
answer += 2 * Math.min(count[i][j], count[j][i]);238Please respect copyright.ＰＥＮＡＮＡVL9aXyTill
}238Please respect copyright.ＰＥＮＡＮＡnh0rNl24Sq
}238Please respect copyright.ＰＥＮＡＮＡ1NsFHfqdcJ
if (central) {238Please respect copyright.ＰＥＮＡＮＡBqZWrl0UkF
answer++;238Please respect copyright.ＰＥＮＡＮＡlpaS1eFZAy
}238Please respect copyright.ＰＥＮＡＮＡuhviaWdm8h
return 2 * answer;238Please respect copyright.ＰＥＮＡＮＡmXj7v7LFDj
}238Please respect copyright.ＰＥＮＡＮＡPfRQRPjqYa
}
238Please respect copyright.ＰＥＮＡＮＡ0RWOOK6loL
然後按「加至主畫面」