JAVA 牛牛

409. 最长回文串

  • Mar 19, 2020
  • 0 views
  • 难度：简单
  • 本题涉及算法： 哈希表 数组 贪心
  • 思路：哈希表 检查区域 贪心
  • 类似题型:

题目 最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

示例

输入:"abccccdd"
输出:7
解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

注意:

  • 假设字符串的长度不会超过 1010。

解题思路 方法一

  • 参考了 拼写单词 构造长度为58的每个元素分别代表一个字母的数组，来简化计算
  • 含大小写 长度58，只有大写或小写大小26
  • 友情提示：遇到有提示字符串仅包含小写（或者大写）英文字母的题,都可以试着考虑能不能构造长度为26的每个元素分别代表一个字母的数组，来简化计算

代码

public class Solution {
    public int longestPalindrome(String s) {
        int[] c = new int[58];
        for(char cc:s.toCharArray()) {
            c[(int)cc-'A']+=1;
        }
        int res = 0;
        boolean flg = false;
        for(int i = 0; i<58; i++) {
            if(c[i]%2==0&&c[i]!=0){
                res+=c[i];
                // flg = true;
            }
            if(c[i]%2==1){
                res+=c[i]-1;
                flg = true;
            }
        }
        if (flg) {
            return res+1;
        }else {
            return res;
        }
    }
}

方法二 哈希表

代码

class Solution(object):
    def longestPalindrome(self, s):
        di = {}
        max = 0
        for ch in s:
            if ch in di:
                di[ch] +=  1
            else:
                di[ch] = 1
        flag = 0
        for d in di:
            if di[d]%2==1:
                flag = 1
                max += di[d]- di[d]%2
            else:
                max += di[d]
        if flag ==1 or len(s)%2==1:
            max += 1
        else:
            return max

        return max

方法三：贪心

  • 构造长度为58的每个元素分别代表一个字母的数组

    代码

    public class Solution {
  public int longestPalindrome(String s) {
      int[] count = new int[128];
      for (char c: s.toCharArray())
          count[c]++;

      int ans = 0;
      for (int v: count) {
          ans += v / 2 * 2;
          if (v % 2 == 1 && ans % 2 == 0)
              ans++;
      }
      return ans;
  }
}

一些高级写法

class Solution:
    def longestPalindrome(self, s: str) -> int:
        import collections
        # 1.统计各字符次数，eg:"ddsad":[3, 1, 1]
        count = collections.Counter(s).values()
        # 2.统计两两配对的字符总个数，eg: {"ddass":4,"ddsss":4}
        x = sum([item//2*2 for item in count if (item//2 > 0)])
        # 3.判断是否有没配对的单字符，有结果加一。 eg: {"ddss":4, "ddhjSS":4+1}-->{"ddss":4, "ddhjSS":5}
        return x if x == len(s) else x+1

class Solution {
    public int longestPalindrome(String s) {
      Map<Integer, Integer> count = s.chars().boxed()
            .collect(Collectors.toMap(k -> k, v -> 1, Integer::sum));

      int ans = count.values().stream().mapToInt(i -> i - (i & 1)).sum();
      return ans < s.length() ? ans + 1 : ans;
    }
}

错误集

class Solution(object):
    def longestPalindrome(self, s):
        di = {}
        max = 0
        for ch in s:
            if ch in di:
                di[ch] +=  1
            else:
                di[ch] = 1
        flag = 0
        for d in di:
            if di[d]//2> 0: # 忽略了相同字母大于3  输出比预期小1
                max += 2 * (di[d]//2)
            else:
                flag = 1 # 说明有落单的字母
        if flag == 1 or len(s)%2==1:
            max += 1
        else:
            return max

        return max

class Solution(object):
    def longestPalindrome(self, s):
        if len(s) <2:
            return 1
        di = {}
        max = 0
        for ch in s:
            if ch in di:
                di[ch] +=  1
            else:
                di[ch] = 1
        flag = 0
        flag2 = 0
        for d in di:
            if di[d]//2> 0:
                flag = 1
                max += 2 * (di[d]//2)
            else:
                flag2 = 1
        if flag ==1 and flag2 == 1 or len(s)%2==1: # 忽略当 s= ab  输出0 预期1
            max += 1
        else:
            return max

        return max

class Solution(object):
    def longestPalindrome(self, s):
        if len(s) <2:
            return 1
        di = {}
        max = 0
        for ch in s:
            if ch in di:
                di[ch] +=  1
            else:
                di[ch] = 1
        flag = 0
        flag2 = 0
        for d in di:
            if di[d]//2> 0: # 忽略了 当 s = bbb 4  输出2 预期3
                flag = 1
                max += 2 * (di[d]//2)
            else:
                flag2 = 1
        if flag ==1 and flag2 == 1:
            max += 1
        else:
            return max

        return max

class Solution(object):
    def longestPalindrome(self, s):
        if len <2:
            return 1
        di = {}
        max = 0
        for ch in s:
            if ch in di:
                di[ch] +=  1
            else:
                di[ch] = 1
        flag = 0
        flag2 = 0
        for d in di:
            if di[d]//2> 0:
                flag = 1
                max += 2 * (di[d]//2)
            else:
                flag2 = 1
        if flag ==1 and flag2 == 1: # 忽略了 当 s=a 时 输出0 预期1
            max += 1
        else:
            return max

        return max
Search