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 {244Please respect copyright.ＰＥＮＡＮＡx9HSk56w82
public int longestPalindrome(String[] words) {244Please respect copyright.ＰＥＮＡＮＡvu6mcUOCbt
HashMap<String, Integer> count = new HashMap<String, Integer>();244Please respect copyright.ＰＥＮＡＮＡaUD3kOanqK
// Count the number of occurrences of each word using a hashmap244Please respect copyright.ＰＥＮＡＮＡfN7MWEIds4
for (String word : words) {244Please respect copyright.ＰＥＮＡＮＡOacCKv0fWN
Integer countOfTheWord = count.get(word);244Please respect copyright.ＰＥＮＡＮＡScic2IECmb
if (countOfTheWord == null) {244Please respect copyright.ＰＥＮＡＮＡg8NoJ0JEio
count.put(word, 1);244Please respect copyright.ＰＥＮＡＮＡ5r8yY6Elej
} else {244Please respect copyright.ＰＥＮＡＮＡmnr350tAEu
count.put(word, countOfTheWord + 1);244Please respect copyright.ＰＥＮＡＮＡZzq5xOW25Z
}244Please respect copyright.ＰＥＮＡＮＡC5jOWiUgcH
}244Please respect copyright.ＰＥＮＡＮＡWlI6esevxo
// 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 word244Please respect copyright.ＰＥＮＡＮＡj2iUQsaui4
int answer = 0;244Please respect copyright.ＰＥＮＡＮＡQwk0dO9ZMm
boolean central = false;244Please respect copyright.ＰＥＮＡＮＡzCipQv2Yf6
for (Map.Entry<String, Integer> entry : count.entrySet()) {244Please respect copyright.ＰＥＮＡＮＡWnAOzP4Qux
String word = entry.getKey();244Please respect copyright.ＰＥＮＡＮＡQvSlKVI4wb
int countOfTheWord = entry.getValue();244Please respect copyright.ＰＥＮＡＮＡZ4bMOEhhWs
// if the word is a palindrome244Please respect copyright.ＰＥＮＡＮＡ6Xs48eZSez
if (word.charAt(0) == word.charAt(1)) {244Please respect copyright.ＰＥＮＡＮＡQNLU9u8tV2
if (countOfTheWord % 2 == 0) {244Please respect copyright.ＰＥＮＡＮＡveIC317QIF
answer += countOfTheWord;244Please respect copyright.ＰＥＮＡＮＡ72LMkqklTH
} else {244Please respect copyright.ＰＥＮＡＮＡlDaiibPnlh
answer += countOfTheWord - 1;244Please respect copyright.ＰＥＮＡＮＡHazL61mZXr
central = true;244Please respect copyright.ＰＥＮＡＮＡdV9QGsXe4l
}244Please respect copyright.ＰＥＮＡＮＡTMErQtHuRg
// consider a pair of non-palindrome words such that one is the reverse of another244Please respect copyright.ＰＥＮＡＮＡXY1SAwkhn8
} else if (word.charAt(0) < word.charAt(1)) {244Please respect copyright.ＰＥＮＡＮＡiNkUkBoZcv
String reversedWord = "" + word.charAt(1) + word.charAt(0);244Please respect copyright.ＰＥＮＡＮＡXVlWWZaPjc
if (count.containsKey(reversedWord)) {244Please respect copyright.ＰＥＮＡＮＡ8JuVn89oqB
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));244Please respect copyright.ＰＥＮＡＮＡYjKEDiq5DS
}244Please respect copyright.ＰＥＮＡＮＡ8w8xSy0Bl1
}244Please respect copyright.ＰＥＮＡＮＡsd8xjSTMGQ
}244Please respect copyright.ＰＥＮＡＮＡg5F5eIMT3w
if (central) {244Please respect copyright.ＰＥＮＡＮＡ7kpd56CC29
answer++;244Please respect copyright.ＰＥＮＡＮＡ2uQo4K50BH
}244Please respect copyright.ＰＥＮＡＮＡHLqdTsjUcM
return 2 * answer;244Please respect copyright.ＰＥＮＡＮＡSZaAEpJvG3
}244Please respect copyright.ＰＥＮＡＮＡeQOzNIK1yq
}
2: A Two-Dimensional Array Approach
class Solution {244Please respect copyright.ＰＥＮＡＮＡpycWRPowXX
public int longestPalindrome(String[] words) {244Please respect copyright.ＰＥＮＡＮＡU9CV7as3kw
final int alphabetSize = 26;244Please respect copyright.ＰＥＮＡＮＡ9qANwckFIX
int[][] count = new int[alphabetSize][alphabetSize];244Please respect copyright.ＰＥＮＡＮＡiyW1Kpe0b9
// Count the number of occurrences of each word using a two-dimensional array. 244Please respect copyright.ＰＥＮＡＮＡrolnumxOxT
for (String word : words) {244Please respect copyright.ＰＥＮＡＮＡWochSwfoSP
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;244Please respect copyright.ＰＥＮＡＮＡT2hiX2Pr5w
}244Please respect copyright.ＰＥＮＡＮＡJIUikfmHVD
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word244Please respect copyright.ＰＥＮＡＮＡtEiA6vU1kp
int answer = 0;244Please respect copyright.ＰＥＮＡＮＡgjgIBNgY4k
boolean central = false;244Please respect copyright.ＰＥＮＡＮＡGolwfIagEp
for (int i = 0; i < alphabetSize; i++) {244Please respect copyright.ＰＥＮＡＮＡ6YzsDrRkeQ
if (count[i][i] % 2 == 0) {244Please respect copyright.ＰＥＮＡＮＡZi8cVPNl48
answer += count[i][i];244Please respect copyright.ＰＥＮＡＮＡNkP4elDKxo
} else {244Please respect copyright.ＰＥＮＡＮＡK6EkTjRSC7
answer += count[i][i] - 1;244Please respect copyright.ＰＥＮＡＮＡZ6FX25MSwE
central = true;244Please respect copyright.ＰＥＮＡＮＡwckNQhPmmf
}244Please respect copyright.ＰＥＮＡＮＡfYdrEepXjB
for (int j = i + 1; j < alphabetSize; j++) {244Please respect copyright.ＰＥＮＡＮＡ3toe8V9ngd
answer += 2 * Math.min(count[i][j], count[j][i]);244Please respect copyright.ＰＥＮＡＮＡ8hJapcKflU
}244Please respect copyright.ＰＥＮＡＮＡQY52DhvAES
}244Please respect copyright.ＰＥＮＡＮＡjv1Yfi8as3
if (central) {244Please respect copyright.ＰＥＮＡＮＡla2IpDvkBA
answer++;244Please respect copyright.ＰＥＮＡＮＡFxSkdLLL4i
}244Please respect copyright.ＰＥＮＡＮＡgmDzBQVoP6
return 2 * answer;244Please respect copyright.ＰＥＮＡＮＡuEqoJRjEHD
}244Please respect copyright.ＰＥＮＡＮＡEP3BJSHskc
}
244Please respect copyright.ＰＥＮＡＮＡFAu6NlRwvC
然後按「加至主畫面」