409. 最长回文串(简单)

Posted on In Views:

1，问题描述

409. 最长回文串

难度：简单

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的 回文串 的长度。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

示例 1:

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

示例 2:

1
2
3
输入:s = "a"
输出:1
解释：可以构造的最长回文串是"a"，它的长度是 1。

提示:

  • 1 <= s.length <= 2000
  • s 只由小写 和/或 大写英文字母组成

2，初步思考

​ 题目是一个简单题，但是我却把题目要解决的问题看错了。。。

选定字符串之后，顺序可以随意调换

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.*;

public class _409最长回文串 {

    public int longestPalindrome_area_v2(String s) {
        int[] dp = new int[128];
        for (char c : s.toCharArray()) dp[c]++;
        int oddCnt = 0;
        for (int i = 0; i < 128; i++) if (dp[i] % 2 == 1) oddCnt++;
        return s.length() - oddCnt + (oddCnt > 0 ? 1 : 0);
    }

    // 解法
    public int longestPalindrome_area(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int max = 0;
        boolean hasOdd = false;
        for (Character c : map.keySet()) {
            if (map.get(c) % 2 == 0) {
                max += map.get(c);
            } else {
                hasOdd = true;
                max += map.get(c) - 1;
            }
        }
        return max + (hasOdd ? 1 : 0);
    }

    // 1. 暴力法：遍历所有可能的回文串，判断是否是回文串，然后取最大值(错误)
    // 题目要解决的问题都没有看好！！！
    public int longestPalindrome_brute(String s) {
        char[] charArray = s.toCharArray();
        int len = charArray.length;
        int left = 0, right = 0;
        int max = 1;
        for (int i = 0; i < len; i++) {
            left = i;
            right = i;
            while (left > 0 && charArray[left - 1] == charArray[right]) {
                left--;
            }
            while (right < len - 1 && charArray[left] == charArray[right + 1]) {
                right++;
                i = right;// 相同的数据，没必要二次计算
            }
            while (left > 0 && right < len - 1 && charArray[left - 1] == charArray[right + 1]) {
                left--;
                right++;
            }
            max = Math.max(max, right - left + 1);
        }
        return max;
    }

    // 模式识别：解决回文问题，直接使用单调栈（monostone stack）（错误）
    public int longestPalindrome(String s) {
        char[] charArray = s.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        stack.push('0');
        int max = 1;
        for (char c : charArray) {

        }
        return max;
    }
}
/**
 * abbcdda
 * abbcbba
 */

4，参考链接

wqs二分优秀做法