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 {196Please respect copyright.ＰＥＮＡＮＡChcfrNoNhJ
public int longestPalindrome(String[] words) {196Please respect copyright.ＰＥＮＡＮＡQs1JWiWDX4
HashMap<String, Integer> count = new HashMap<String, Integer>();196Please respect copyright.ＰＥＮＡＮＡmmt8moADG8
// Count the number of occurrences of each word using a hashmap196Please respect copyright.ＰＥＮＡＮＡFsAZqg07Tz
for (String word : words) {196Please respect copyright.ＰＥＮＡＮＡZdZLoMVDh0
Integer countOfTheWord = count.get(word);196Please respect copyright.ＰＥＮＡＮＡjXN6a9TWIb
if (countOfTheWord == null) {196Please respect copyright.ＰＥＮＡＮＡACX2f2KBRM
count.put(word, 1);196Please respect copyright.ＰＥＮＡＮＡVwKJEcXc6o
} else {196Please respect copyright.ＰＥＮＡＮＡnkyTPdcIJR
count.put(word, countOfTheWord + 1);196Please respect copyright.ＰＥＮＡＮＡUju2853uQl
}196Please respect copyright.ＰＥＮＡＮＡXicedWzf39
}196Please respect copyright.ＰＥＮＡＮＡc58vaBOxbb
// 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 word196Please respect copyright.ＰＥＮＡＮＡY2MAKAEOiX
int answer = 0;196Please respect copyright.ＰＥＮＡＮＡlXVaVmsn6Z
boolean central = false;196Please respect copyright.ＰＥＮＡＮＡ2GZssvXXkR
for (Map.Entry<String, Integer> entry : count.entrySet()) {196Please respect copyright.ＰＥＮＡＮＡAspgoFQHct
String word = entry.getKey();196Please respect copyright.ＰＥＮＡＮＡ0fjXg72PgR
int countOfTheWord = entry.getValue();196Please respect copyright.ＰＥＮＡＮＡrkN0iL0XOy
// if the word is a palindrome196Please respect copyright.ＰＥＮＡＮＡeMm3RfdscK
if (word.charAt(0) == word.charAt(1)) {196Please respect copyright.ＰＥＮＡＮＡkMrqaseWm9
if (countOfTheWord % 2 == 0) {196Please respect copyright.ＰＥＮＡＮＡzCTKQYBs5a
answer += countOfTheWord;196Please respect copyright.ＰＥＮＡＮＡJRUSNO3EEQ
} else {196Please respect copyright.ＰＥＮＡＮＡcVYpahVVOv
answer += countOfTheWord - 1;196Please respect copyright.ＰＥＮＡＮＡhVhMxt2hIO
central = true;196Please respect copyright.ＰＥＮＡＮＡDSqHQTPNeR
}196Please respect copyright.ＰＥＮＡＮＡlxnnDXSDnj
// consider a pair of non-palindrome words such that one is the reverse of another196Please respect copyright.ＰＥＮＡＮＡsqF2EJA2ar
} else if (word.charAt(0) < word.charAt(1)) {196Please respect copyright.ＰＥＮＡＮＡXc7MBt0I0E
String reversedWord = "" + word.charAt(1) + word.charAt(0);196Please respect copyright.ＰＥＮＡＮＡLATgZWe1VK
if (count.containsKey(reversedWord)) {196Please respect copyright.ＰＥＮＡＮＡ9IRpwAhEsa
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));196Please respect copyright.ＰＥＮＡＮＡWH0UxvgF5f
}196Please respect copyright.ＰＥＮＡＮＡR6IXA6Wltn
}196Please respect copyright.ＰＥＮＡＮＡS4v3t3sQKX
}196Please respect copyright.ＰＥＮＡＮＡNyus4eBCZy
if (central) {196Please respect copyright.ＰＥＮＡＮＡr85BDfEXNP
answer++;196Please respect copyright.ＰＥＮＡＮＡ4h76n5pmpt
}196Please respect copyright.ＰＥＮＡＮＡr2uG4Jtf2I
return 2 * answer;196Please respect copyright.ＰＥＮＡＮＡAE00ELerc0
}196Please respect copyright.ＰＥＮＡＮＡC6WhMIvM9Y
}
2: A Two-Dimensional Array Approach
class Solution {196Please respect copyright.ＰＥＮＡＮＡ62y0uhMTKo
public int longestPalindrome(String[] words) {196Please respect copyright.ＰＥＮＡＮＡk3UZqHUEyp
final int alphabetSize = 26;196Please respect copyright.ＰＥＮＡＮＡObBdcTYXkS
int[][] count = new int[alphabetSize][alphabetSize];196Please respect copyright.ＰＥＮＡＮＡ7NnYMZhnH0
// Count the number of occurrences of each word using a two-dimensional array. 196Please respect copyright.ＰＥＮＡＮＡmvjEiG9sDW
for (String word : words) {196Please respect copyright.ＰＥＮＡＮＡyGSdQcryxg
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;196Please respect copyright.ＰＥＮＡＮＡEPDtUu7Yxc
}196Please respect copyright.ＰＥＮＡＮＡ38iRl0uZPi
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word196Please respect copyright.ＰＥＮＡＮＡWbMvmIF8gL
int answer = 0;196Please respect copyright.ＰＥＮＡＮＡ2KzBxckC5Y
boolean central = false;196Please respect copyright.ＰＥＮＡＮＡoEKWRzvojP
for (int i = 0; i < alphabetSize; i++) {196Please respect copyright.ＰＥＮＡＮＡT1fOMWRoPg
if (count[i][i] % 2 == 0) {196Please respect copyright.ＰＥＮＡＮＡEBhakwjWHw
answer += count[i][i];196Please respect copyright.ＰＥＮＡＮＡmH7bvPCZdM
} else {196Please respect copyright.ＰＥＮＡＮＡC2GpGpxwy2
answer += count[i][i] - 1;196Please respect copyright.ＰＥＮＡＮＡpvP14lp9li
central = true;196Please respect copyright.ＰＥＮＡＮＡU3aqFJ2RNX
}196Please respect copyright.ＰＥＮＡＮＡQZjod2KW4L
for (int j = i + 1; j < alphabetSize; j++) {196Please respect copyright.ＰＥＮＡＮＡI1n4Kaf6Xr
answer += 2 * Math.min(count[i][j], count[j][i]);196Please respect copyright.ＰＥＮＡＮＡyyCpADEvm1
}196Please respect copyright.ＰＥＮＡＮＡRJTgzPyIPm
}196Please respect copyright.ＰＥＮＡＮＡ0qpfj9Nm4P
if (central) {196Please respect copyright.ＰＥＮＡＮＡ14X2WF23x5
answer++;196Please respect copyright.ＰＥＮＡＮＡ1MyB62SXa5
}196Please respect copyright.ＰＥＮＡＮＡqf8ZHbKRYk
return 2 * answer;196Please respect copyright.ＰＥＮＡＮＡ4SdAOG0f9t
}196Please respect copyright.ＰＥＮＡＮＡ2tm7lbEqaU
}
196Please respect copyright.ＰＥＮＡＮＡAkQmjHX1Ao
然後按「加至主畫面」