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 {275Please respect copyright.ＰＥＮＡＮＡF2M0kVuNUR
public int longestPalindrome(String[] words) {275Please respect copyright.ＰＥＮＡＮＡTOiDINdVr3
HashMap<String, Integer> count = new HashMap<String, Integer>();275Please respect copyright.ＰＥＮＡＮＡqRgEGxB9Hj
// Count the number of occurrences of each word using a hashmap275Please respect copyright.ＰＥＮＡＮＡRHzJGgPlSj
for (String word : words) {275Please respect copyright.ＰＥＮＡＮＡfpOzdaSAbk
Integer countOfTheWord = count.get(word);275Please respect copyright.ＰＥＮＡＮＡH20QkVi9w9
if (countOfTheWord == null) {275Please respect copyright.ＰＥＮＡＮＡdrfHfilTXU
count.put(word, 1);275Please respect copyright.ＰＥＮＡＮＡjdADR9QlSQ
} else {275Please respect copyright.ＰＥＮＡＮＡHyCkl1G4CY
count.put(word, countOfTheWord + 1);275Please respect copyright.ＰＥＮＡＮＡ9djmTdobwu
}275Please respect copyright.ＰＥＮＡＮＡ1MbQoygFlO
}275Please respect copyright.ＰＥＮＡＮＡDn66xqyNN4
// 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 word275Please respect copyright.ＰＥＮＡＮＡC1RJQzFnhr
int answer = 0;275Please respect copyright.ＰＥＮＡＮＡIIbKYIVpEJ
boolean central = false;275Please respect copyright.ＰＥＮＡＮＡJ0yhEb5a1C
for (Map.Entry<String, Integer> entry : count.entrySet()) {275Please respect copyright.ＰＥＮＡＮＡLjvXJ2ycZt
String word = entry.getKey();275Please respect copyright.ＰＥＮＡＮＡTGY7ikEz7K
int countOfTheWord = entry.getValue();275Please respect copyright.ＰＥＮＡＮＡReUXhHcAE9
// if the word is a palindrome275Please respect copyright.ＰＥＮＡＮＡmPG5YdzMX2
if (word.charAt(0) == word.charAt(1)) {275Please respect copyright.ＰＥＮＡＮＡjWwti3GqtQ
if (countOfTheWord % 2 == 0) {275Please respect copyright.ＰＥＮＡＮＡZRn8F3FdjT
answer += countOfTheWord;275Please respect copyright.ＰＥＮＡＮＡ6ruRE6qsQt
} else {275Please respect copyright.ＰＥＮＡＮＡie3Z66Baak
answer += countOfTheWord - 1;275Please respect copyright.ＰＥＮＡＮＡJADSLMo4i4
central = true;275Please respect copyright.ＰＥＮＡＮＡrkP3DXQDs8
}275Please respect copyright.ＰＥＮＡＮＡtR9rEWNr8k
// consider a pair of non-palindrome words such that one is the reverse of another275Please respect copyright.ＰＥＮＡＮＡ3i7wznwQP3
} else if (word.charAt(0) < word.charAt(1)) {275Please respect copyright.ＰＥＮＡＮＡqiWxEyfOVT
String reversedWord = "" + word.charAt(1) + word.charAt(0);275Please respect copyright.ＰＥＮＡＮＡMnMGa1AXpb
if (count.containsKey(reversedWord)) {275Please respect copyright.ＰＥＮＡＮＡR7QPVaswTm
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));275Please respect copyright.ＰＥＮＡＮＡe6poS0AxhF
}275Please respect copyright.ＰＥＮＡＮＡcB1Ux18AYt
}275Please respect copyright.ＰＥＮＡＮＡXw4uNL4fPI
}275Please respect copyright.ＰＥＮＡＮＡ1Mc0KixKT5
if (central) {275Please respect copyright.ＰＥＮＡＮＡLlfw9w31xR
answer++;275Please respect copyright.ＰＥＮＡＮＡCm7rcQDp2p
}275Please respect copyright.ＰＥＮＡＮＡni8fIjksDp
return 2 * answer;275Please respect copyright.ＰＥＮＡＮＡVgBPqCA3GM
}275Please respect copyright.ＰＥＮＡＮＡyhOfdbZZHE
}
2: A Two-Dimensional Array Approach
class Solution {275Please respect copyright.ＰＥＮＡＮＡYdn8NQgzgj
public int longestPalindrome(String[] words) {275Please respect copyright.ＰＥＮＡＮＡtNyahTyoPv
final int alphabetSize = 26;275Please respect copyright.ＰＥＮＡＮＡxOWGDp18wf
int[][] count = new int[alphabetSize][alphabetSize];275Please respect copyright.ＰＥＮＡＮＡZ0vuMnhxfP
// Count the number of occurrences of each word using a two-dimensional array. 275Please respect copyright.ＰＥＮＡＮＡJ9Nff5Pfkd
for (String word : words) {275Please respect copyright.ＰＥＮＡＮＡpSOmDcH7Lm
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;275Please respect copyright.ＰＥＮＡＮＡfpNnYoERQy
}275Please respect copyright.ＰＥＮＡＮＡlC2cfrRLiJ
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word275Please respect copyright.ＰＥＮＡＮＡLNSn8dTH9J
int answer = 0;275Please respect copyright.ＰＥＮＡＮＡxhZ9PSlsW6
boolean central = false;275Please respect copyright.ＰＥＮＡＮＡkIt37VtDbk
for (int i = 0; i < alphabetSize; i++) {275Please respect copyright.ＰＥＮＡＮＡuFSYL5gHfu
if (count[i][i] % 2 == 0) {275Please respect copyright.ＰＥＮＡＮＡQ5jx56iMSx
answer += count[i][i];275Please respect copyright.ＰＥＮＡＮＡVh8xKYyNU0
} else {275Please respect copyright.ＰＥＮＡＮＡiFaiyNs1QE
answer += count[i][i] - 1;275Please respect copyright.ＰＥＮＡＮＡy9G6VAizKL
central = true;275Please respect copyright.ＰＥＮＡＮＡ3NLCfqmKAC
}275Please respect copyright.ＰＥＮＡＮＡ0QgTsl30A2
for (int j = i + 1; j < alphabetSize; j++) {275Please respect copyright.ＰＥＮＡＮＡeJyEtvENhX
answer += 2 * Math.min(count[i][j], count[j][i]);275Please respect copyright.ＰＥＮＡＮＡLp7RZvMbFc
}275Please respect copyright.ＰＥＮＡＮＡTyDnJ6jQlw
}275Please respect copyright.ＰＥＮＡＮＡZOENWXQOq1
if (central) {275Please respect copyright.ＰＥＮＡＮＡHfQ6O9tfSi
answer++;275Please respect copyright.ＰＥＮＡＮＡ3gKXO8ZB6l
}275Please respect copyright.ＰＥＮＡＮＡa13ONuOey6
return 2 * answer;275Please respect copyright.ＰＥＮＡＮＡlre0OYBcbw
}275Please respect copyright.ＰＥＮＡＮＡWdURUmMUWz
}
275Please respect copyright.ＰＥＮＡＮＡo28z85yBqo
然後按「加至主畫面」