6
#yyds干货盘点# leetcode算法题：连接两字母单词得到的最长回文串
source link: https://blog.51cto.com/u_13321676/5590789
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# leetcode算法题：连接两字母单词得到的最长回文串
精选 原创给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。
请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。
请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。
回文串 指的是从前往后和从后往前读一样的字符串。
输入：words = ["lc","cl","gg"]
解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
"clgglc" 是另一个可以得到的最长回文串。
输入：words = ["ab","ty","yt","lc","cl","ab"]
解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。
"lcyttycl" 是另一个可以得到的最长回文串。
输入：words = ["cc","ll","xx"]
解释：最长回文串是 "cc" ，长度为 2 。
"ll" 是另一个可以得到的最长回文串。"xx" 也是。
代码实现：
public int longestPalindrome(String[] words) {
Map<String,Integer> map=new HashMap<>();
for(int i=0;i<words.length;i++){map.put(words[i],map.getOrDefault(words[i],0)+1);}
int add=0;
int ans=0;
for(String s:map.keySet()){
if(s.charAt(0)==s.charAt(1)){
ans+=((map.get(s)>>1)<<2);
if(((map.get(s)&1)==1)){add=2;}
}
else{
String t=pal(s);
if(map.containsKey(t)){ans+=Math.min(map.get(s),map.get(t))*2;}
}
}
return ans+add;
}
public String pal(String s){
return new StringBuilder(s).reverse().toString();
}
Map<String,Integer> map=new HashMap<>();
for(int i=0;i<words.length;i++){map.put(words[i],map.getOrDefault(words[i],0)+1);}
int add=0;
int ans=0;
for(String s:map.keySet()){
if(s.charAt(0)==s.charAt(1)){
ans+=((map.get(s)>>1)<<2);
if(((map.get(s)&1)==1)){add=2;}
}
else{
String t=pal(s);
if(map.containsKey(t)){ans+=Math.min(map.get(s),map.get(t))*2;}
}
}
return ans+add;
}
public String pal(String s){
return new StringBuilder(s).reverse().toString();
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK