作者微信
微

#yyds干货盘点# leetcode算法题：连接两字母单词得到的最长回文串

小技术 7个月前 (08-19) 0 999+

关注

题目：

给你一个字符串数组 words 。words 中每个元素都是一个包含两个小写英文字母的单词。

请你从 words 中选择一些元素并按任意顺序连接它们，并得到一个尽可能长的回文串。每个元素至多只能使用一次。

请你返回你能得到的最长回文串的长度。如果没办法得到任何一个回文串，请你返回 0 。

回文串指的是从前往后和从后往前读一样的字符串。

示例 1：

输入：words = ["lc","cl","gg"]

输出：6

解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。

"clgglc" 是另一个可以得到的最长回文串。

示例 2：

输入：words = ["ab","ty","yt","lc","cl","ab"]

输出：8

解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。

"lcyttycl" 是另一个可以得到的最长回文串。

示例 3：

输入：words = ["cc","ll","xx"]

输出：2

解释：最长回文串是 "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();
    }