【字符串】最长回文子串 ( 动态规划算法 ) ★

韩曙亮

发布于 2023-03-29 14:47:45

6290

发布于 2023-03-29 14:47:45

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、回文串、子串、子序列

" 回文串 ( Palindrome ) " 是正反都一样的字符串 , abccba , 001100 等字符串 ;

给定一个字符串 " abcd " ,

" 子串 ( SubString ) "是连续取的子字符串 , 如 : “ab” , “bc” , “cd” , “bcd” 等 , 不能跳跃字符 ; ( 连续字符 )

个字符串的子串个数是

\cfrac{n(n+1)}{2} +1

个 ;

" 子序列 ( SubSequence ) " 是可以非连续取字符串中的字符 , 前后顺序不允许颠倒 , 如 “ad” , “bd” , “acd” 等 ; ( 非连续字符 )

个字符串的子串个数是

2^n

个 ( 集合的子集数 ) ;

验证一个字符串是否是回文串 , 最坏的情况下需要遍历

\cfrac{n}{2}

次 ;

因此最暴力的方法验证回文子串 , 就是验证

\cfrac{n(n+1)}{2} +1

个子字符串是否是回文串 , 每次都要遍历

\cfrac{n}{2}

次 ; 暴力算法的时间复杂度是

O(n^3)

;

二、最长回文子串

问题链接 : https://www.lintcode.com/problem/200/description

给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。

1、动态规划算法

如果不使用中心线枚举算法 , 在蛮力算法的基础上 , 快速判定字符串是否是回文串 ; 使用基于动态规划的算法可以实现上述要求 ;

回文串存在特点 : 两种类型的回文串 “abba” , “abcba” , 正序和倒序是一样的 ; 回文串两头的字符相等 ; 回文串除去两头的两个字符 , 中间部分也是回文串 ;

字符串中

之间的字符串是回文串 ;

i, j

字符相等 ,

并且

i +1

j - 1

的字符串也是回文串 ;

之间的字符串是否是回文串 , 依赖于

i +1

j - 1

之间的字符串是否是回文串 ; 因此推导任意两个索引区间

i, j

之间的字符串是否是回文串时 ,

将

i, j

之间的字符串是否是回文串 , 存储在一个二维布尔数组中 ;

// 表示 n 个字符串中所有的字符索引之间是否是回文串 
boolean [][] isPalindrome = new boolean[n][n];

isPalindrome[i][j] 表示

之间的字符串是否是回文串 , 如果是回文串则设置为 true , 如果不是回文串则设置为 false ;

回文串判定条件 :

isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);

之间的字符串是回文串 , 则

i +1

j - 1

之间的字符串也是回文串 , 并且第

个字符等于第

个字符 ;

动态规划 :

这种推导公式在动态规划中 , 称为状态转移方程 ;

isPalindrome 二维数组中每个元素都是一个状态 , 这个状态是以区间作为状态的标志 , 两个维度的值分别是区间的开始索引和结束索引 ;

这种类型的动态规划 , 又称为 区间型动态规划 ;

循环设计 :

之间的字符串是否是回文串 , 依赖于

i +1

j - 1

之间的字符串是否是回文串 ;

也就是

依赖于

i + 1

, 循环时 , 不能正向循环 , 只能倒序循环 ;

先计算

比较大的 , 再计算

比较小的 ;

初始化操作 : 动态规划中初始化很重要 ;

这里要考虑公式的适用性 , 上述公式

isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);

公式中使用了

i + 1

j - 1

, 为了保证公式成立 , 字符串的字符个数至少要有

个 ;

初始化时最好将空字符串 ,

个字符组成的字符串的情况直接初始化赋值 ;

初始化单个字符字符串的状态 :

isPalindrome[i][i] 是第

个字符到第

个字符之间的单个字符是否是回文串 , 显然单个字符是回文串 ;

isPalindrome[i][i] = true

2、动态规划算法代码示例

代码示例 :

class Solution {
    /**
     * @param s: 输入字符串
     * @return: 返回最长回文子串
     */
    public String longestPalindrome(String s) {
        if (s == null || "".equals(s)) {
            return null;
        }

        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        int longest = 1;    // 最长长度
        int start = 0;      // 开始索引

        // 初始化操作, 长度为 1 的回文串
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
        }

		// 初始化操作, 长度为 2 的回文串
        for (int i = 0; i < n - 1; i ++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                isPalindrome[i][i + 1] = true;
                start = i;
                longest = 2;
            }else {
                isPalindrome[i][i + 1] = false;
            }
        }

		// 倒序遍历
        for (int i = n - 1; i >= 0; i--) {
        	// 从 i + 2 开始计算 , 之前 i , i + 1 都已经计算过了 , 从长度为 3 的区间开始计算
        	// 注意此处如果 j >= n 时 , 不进入内层循环 
        	// 只有在 j <= n - 1 时 , 才进入内层循环 
            for (int j = i + 2; j < n; j ++) {
                isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);

                if (isPalindrome[i][j] && j - i + 1 > longest) {
                    start = i;
                    longest = j - i + 1;
                }
            }
        }

        return s.substring(start, start + longest);
    }
}

class Main {
    public static void main(String[] args) {
        String palindrome = new Solution().longestPalindrome("mabcban");
        System.out.println(palindrome);
    }
}

O(n^2)

时间复杂度算法;