【字符串】最长回文子串 ( 蛮力算法 )

韩曙亮

发布于 2023-03-29 12:55:03

9400

发布于 2023-03-29 12:55:03

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

文章目录

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

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

给定一个字符串 " abcd " ,

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

个字符串的子串个数是

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

个 ;

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

个字符串的子串个数是

2^n

个 ( 集合的子集数 ) ;

二、最长回文子串

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

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

1、蛮力算法

蛮力算法 :

① 先获取所有的子串 ; 嵌套两层循环 , 外层循环起点索引 , 内层循环终点索引 , 将

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

个子串都遍历出来 ; 该操作是

O(n^2)

的算法复杂度 ;

② 验证子串是否是回文串 ; 使用相向双指针算法 , 设置两个指针 , 左指针指向字符串开始位置 , 右指针指向字符串结束位置 , 对比左右指针是否相等 , 如果相等 , 左指针递增 , 右指针递减 , 继续判定指向的字符是否相等 ; 该操作是

O(n)

的算法复杂度 ;

上述操作总的时间复杂度是

O(n^3)

; 面试的时候写这个算法 , 基本就凉了 ;

嵌套循环 , 外层循环必须从长度最长的开始进行 , 内层循环从

索引开始 ;

代码示例 :

public class Solution {
    /**
     * @param s: input string
     * @return: a string as the longest palindromic substring
     */
    public String longestPalindrome(String s) {
        if (s == null) {
            return null;
        }

        for (int length = s.length(); length > 0; length--) {
            for (int start = 0; length + start <= s.length(); start++) {
                if (isPalindrome(s, start, start + length - 1)) {
                    return s.substring(start, start + length);
                }
            }
        }

        return "";
    }

    private boolean isPalindrome(String s, int left, int right) {
        while(left < right && s.charAt(left) == s.charAt(right)) {
            left++;
            right--;
        }
        return left >= right;
    }
}

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

O(n^3)

时间复杂度算法 , 耗时较长 ;