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 {243Please respect copyright.ＰＥＮＡＮＡbZc6sl3ekZ
public int longestPalindrome(String[] words) {243Please respect copyright.ＰＥＮＡＮＡfeY240nytk
HashMap<String, Integer> count = new HashMap<String, Integer>();243Please respect copyright.ＰＥＮＡＮＡWmVY7qk1K4
// Count the number of occurrences of each word using a hashmap243Please respect copyright.ＰＥＮＡＮＡQqB0UvPUSe
for (String word : words) {243Please respect copyright.ＰＥＮＡＮＡcPBqITFMhu
Integer countOfTheWord = count.get(word);243Please respect copyright.ＰＥＮＡＮＡQ1TVuNalWR
if (countOfTheWord == null) {243Please respect copyright.ＰＥＮＡＮＡVp0CViMejm
count.put(word, 1);243Please respect copyright.ＰＥＮＡＮＡ5QSor7mRup
} else {243Please respect copyright.ＰＥＮＡＮＡX7QmbPl8Hu
count.put(word, countOfTheWord + 1);243Please respect copyright.ＰＥＮＡＮＡA6JenbSl02
}243Please respect copyright.ＰＥＮＡＮＡH8WiKt2sDr
}243Please respect copyright.ＰＥＮＡＮＡLaWdOg9vGI
// 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 word243Please respect copyright.ＰＥＮＡＮＡxebiJcD5uA
int answer = 0;243Please respect copyright.ＰＥＮＡＮＡepdjwOElh6
boolean central = false;243Please respect copyright.ＰＥＮＡＮＡUtB7D3L6J6
for (Map.Entry<String, Integer> entry : count.entrySet()) {243Please respect copyright.ＰＥＮＡＮＡVtBt0dD7g1
String word = entry.getKey();243Please respect copyright.ＰＥＮＡＮＡY7VpxVyEwz
int countOfTheWord = entry.getValue();243Please respect copyright.ＰＥＮＡＮＡtr8URP0wM1
// if the word is a palindrome243Please respect copyright.ＰＥＮＡＮＡUkCGOvrobQ
if (word.charAt(0) == word.charAt(1)) {243Please respect copyright.ＰＥＮＡＮＡkSApzZxN6a
if (countOfTheWord % 2 == 0) {243Please respect copyright.ＰＥＮＡＮＡk3NGTOiTDb
answer += countOfTheWord;243Please respect copyright.ＰＥＮＡＮＡnIdAAmxKNC
} else {243Please respect copyright.ＰＥＮＡＮＡuS7gc81tuj
answer += countOfTheWord - 1;243Please respect copyright.ＰＥＮＡＮＡ45lLdCNWxE
central = true;243Please respect copyright.ＰＥＮＡＮＡd9R2K5XOvp
}243Please respect copyright.ＰＥＮＡＮＡlUL9exnyy0
// consider a pair of non-palindrome words such that one is the reverse of another243Please respect copyright.ＰＥＮＡＮＡVfPTFz7qjI
} else if (word.charAt(0) < word.charAt(1)) {243Please respect copyright.ＰＥＮＡＮＡmkPfccwvpa
String reversedWord = "" + word.charAt(1) + word.charAt(0);243Please respect copyright.ＰＥＮＡＮＡOTwmnSR0Fo
if (count.containsKey(reversedWord)) {243Please respect copyright.ＰＥＮＡＮＡ3CeH5U9IP4
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));243Please respect copyright.ＰＥＮＡＮＡXyorFL3hVF
}243Please respect copyright.ＰＥＮＡＮＡEEpvgSSibL
}243Please respect copyright.ＰＥＮＡＮＡZQjflpIDTf
}243Please respect copyright.ＰＥＮＡＮＡxln2lzEb0U
if (central) {243Please respect copyright.ＰＥＮＡＮＡfTNYUT5IRM
answer++;243Please respect copyright.ＰＥＮＡＮＡgOrg71Wvw2
}243Please respect copyright.ＰＥＮＡＮＡ68eswH9oLG
return 2 * answer;243Please respect copyright.ＰＥＮＡＮＡoKj9VDilJ8
}243Please respect copyright.ＰＥＮＡＮＡ3qBdrpJ5CL
}
2: A Two-Dimensional Array Approach
class Solution {243Please respect copyright.ＰＥＮＡＮＡc9V4I2dbPC
public int longestPalindrome(String[] words) {243Please respect copyright.ＰＥＮＡＮＡKYqXfdTZdx
final int alphabetSize = 26;243Please respect copyright.ＰＥＮＡＮＡC8UK54gD5P
int[][] count = new int[alphabetSize][alphabetSize];243Please respect copyright.ＰＥＮＡＮＡCCAxToCvpD
// Count the number of occurrences of each word using a two-dimensional array. 243Please respect copyright.ＰＥＮＡＮＡVilUuo1OQy
for (String word : words) {243Please respect copyright.ＰＥＮＡＮＡ3VO7rIbrkP
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;243Please respect copyright.ＰＥＮＡＮＡUWg2E5lp2O
}243Please respect copyright.ＰＥＮＡＮＡ4wZPP9KIHn
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word243Please respect copyright.ＰＥＮＡＮＡD2c736pHp9
int answer = 0;243Please respect copyright.ＰＥＮＡＮＡNbZSciS1ai
boolean central = false;243Please respect copyright.ＰＥＮＡＮＡgHkNOa2FBE
for (int i = 0; i < alphabetSize; i++) {243Please respect copyright.ＰＥＮＡＮＡgyE41BQysK
if (count[i][i] % 2 == 0) {243Please respect copyright.ＰＥＮＡＮＡoodjprDNwQ
answer += count[i][i];243Please respect copyright.ＰＥＮＡＮＡJetiHz2TAq
} else {243Please respect copyright.ＰＥＮＡＮＡrkdwtTz4Da
answer += count[i][i] - 1;243Please respect copyright.ＰＥＮＡＮＡcx76fGhg12
central = true;243Please respect copyright.ＰＥＮＡＮＡhCVsDzcIL3
}243Please respect copyright.ＰＥＮＡＮＡfN1neIQ7qE
for (int j = i + 1; j < alphabetSize; j++) {243Please respect copyright.ＰＥＮＡＮＡUCBolhX5Xx
answer += 2 * Math.min(count[i][j], count[j][i]);243Please respect copyright.ＰＥＮＡＮＡfl4JU6AR7u
}243Please respect copyright.ＰＥＮＡＮＡcFhoFyYGri
}243Please respect copyright.ＰＥＮＡＮＡcpsB9BrV8i
if (central) {243Please respect copyright.ＰＥＮＡＮＡ9vicJnEjJI
answer++;243Please respect copyright.ＰＥＮＡＮＡ5RvkZP7NkV
}243Please respect copyright.ＰＥＮＡＮＡxVO6WpgXjn
return 2 * answer;243Please respect copyright.ＰＥＮＡＮＡSKIKQ30cC5
}243Please respect copyright.ＰＥＮＡＮＡdEHD28tHMz
}
243Please respect copyright.ＰＥＮＡＮＡGOROnDtb6X
然後按「加至主畫面」