BluePen BluePen
  • Jenkins
  • OS
  • 算法
随笔
分类
标签
归档
关于
留言板
GitHub (opens new window)

Alex

一个好人
  • Jenkins
  • OS
  • 算法
随笔
分类
标签
归档
关于
留言板
GitHub (opens new window)
  • leetcode

    • 哈希

    • 字符串操作

    • 数字操作

    • 双指针

    • 递归

    • 链表

    • 动态规划

      • 最长上升子序列
      • 最长公共子序列
      • 最长回文子串
        • 题目描述
        • 解法
        • 总结
        • 参考
    • 二分法

  • interview

  • well_known_algo

  • algo
  • leetcode
  • 动态规划
Alex
2019-11-11
目录

最长回文子串

-> 题目描述

Longest Palindromic Substring

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000, 且只包含字母和数字

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
1
2
3
Input: s = "cbbd"
Output: "bb"
1
2
Input: s = "a"
Output: "a"
Example 4:
1
2
3
Input: s = "ac"
Output: "a"
1
2

From leetcode No.5 Medium (opens new window)

class Solution {
    public String longestPalindrome(String s) {
        
    }
}
1
2
3
4
5

-> 解法

暴力循环
class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        int max = 1;
        int begin = 0;
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {

                if (j - i + 1 > max && isPalindrome(arr, i, j)) {
                    max = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + max);
    }

    private boolean isPalindrome(char[] s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
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
动态规划
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        String ans = "";
        for (int n = 0; n < len; n++) {
            for (int i = 0; i + n < len; i++) {
                int j = i + n;
                if (n == 0) { // i==j, dp[i][j] == true
                    dp[i][j] = true;
                } else if (n == 1) { //j = i +1
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else { // j -i > 2
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                }
                if (dp[i][j] && n + 1 > ans.length()) {
                    ans = s.substring(i, j + 1);
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
中心扩散法
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}
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
中心扩散法优化
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        int start = 0;
        int end = 0;
        Character[] arr = new Character[2 * len + 1];
        for (int i = 0; i < arr.length; i++) {
            if (i % 2 == 0) {
                arr[i] = '#';
            } else {
                arr[i] = s.charAt(i / 2);
            }
        }
        for (int i = 0; i < arr.length; i++) {
            int ret = this.expandAroundCenter(arr, i);
            if (ret > end - start) {
                start = i - (ret - 1) / 2;
                end = i + ret / 2;
            }
        }
        if (start % 2 == 0) {
            start = start / 2;
        } else {
            start = (start - 1) / 2;
        }
        if (end % 2 == 0) {
            end = end / 2 - 1;
        } else {
            end = (end - 1) / 2 - 1;
        }
        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(Character[] s, int center) {
        int left = center - 1;
        int right = center + 1;
        while (left >= 0 && right < s.length && s[left] == s[right]) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}
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

-> 总结

  1. 暴力循环
    • 最容易想到的解法,遍历所有子串,判断是否为回文串,是的话记录字符串长度和起始索引
    • 大概有 n*n个子串,每个平均长度为 n/2, 时间复杂度为 n3
  2. 动态规划
    • 假设字符串 s长度为 n, 以一个二维数组 f[i][j](i >= 0, j >= i, j <= n-1) 的布尔值来表示索引 i, i+1, ...j的字符串是否为回文串
    • 如果 f[i][j] 为 true,那么 f[i+1][j-1] 肯定为 true,且 s[i] == s[j]
      • 这里的前提条件是 j>2
    • 特殊的边界条件为 n == 1 或 n == 2
      • f[i][j] 永远为 true (i == j)
      • n == 2, 如果 s[i] == s[j], 则 f[i][j]为 true (j - i = 1)
    • 状态转移方程的推导
      • 字符串 s长度为 1, f[i][j] 永远为 true, 此时最长回文串长度为 1
      • 字符串 s长度为 2, f[i][j],判断 s[i] == s[j], 如果为 true,此时最长回文串长度为 2
      • 字符串 s长度大于 2, f[i][j],判断 f[i+1][j-1] && s[i] === s[j], 如果为 true,此时最长回文串长度为 j-i+1
    • 求最长回文字符串,即 f[i][j] 为 true的前提下,j-i+1为最大值的情况, 得到字符串子串 s[i, j]
  3. 中心扩散法
    • 思想是把当前字符串中的每个元素及每两个元素当作中心,向两边扩散,直到到达边界或不满足回文串的条件
    • 满足回文串条件则记录起点和终点,比较长度即可得到最长回文子串
    • 相比动态规范,该算法降低了空间复杂度
    • 由于回文串的组成,决定了它可能有 1或 2个中心,也可以先将每个字符的前后空隙均填充相同的(原字符串中不存在的)特殊字符
      • eg:#, 这样 n个字符加上 n+1个空隙,就组成了 2n+1固定的奇数个字符的新字符串
      • 新字符串就只可能存在一个中心,可进一步降低时间复杂度
  4. manacher 算法
    • refer to manacher-ago

-> 参考

longest-palindromic-substring (opens new window)

编辑此页 (opens new window)
更新于: 2019-11-11 10:45
最长公共子序列
在排序数组中查找元素的第一个和最后一个位置

← 最长公共子序列 在排序数组中查找元素的第一个和最后一个位置→

Copyright © 2019-2022 | yxxy | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式