【字符串】最长回文子串 ( 中心线枚举算法 )

简介: 【字符串】最长回文子串 ( 中心线枚举算法 )

文章目录

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

二、最长回文子串

1、中心线枚举算法

2、中心线枚举算法代码示例





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


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



给定一个字符串 " abcd " ,


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


n nn 个字符串的子串个数是 n ( n + 1 ) 2 + 1 \cfrac{n(n+1)}{2} +1

2

n(n+1)


+1 个 ;


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


n nn 个字符串的子串个数是 2 n 2^n2

n

 个 ( 集合的子集数 ) ;


验证一个字符串是否是回文串 , 最坏的情况下需要遍历 n 2 \cfrac{n}{2}

2

n


 次 ;


因此最暴力的方法验证回文子串 , 就是验证 n ( n + 1 ) 2 + 1 \cfrac{n(n+1)}{2} +1

2

n(n+1)


+1 个子字符串是否是回文串 , 每次都要遍历 n 2 \cfrac{n}{2}

2

n


 次 ;

暴力算法的时间复杂度是 O ( n 3 ) O(n^3)O(n

3

) ;






二、最长回文子串


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


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




1、中心线枚举算法


中心线枚举算法 :


使用暴力算法 , 算法的复杂度是 O ( n 3 ) O(n^3)O(n

3

) ;


暴力算法中有 性能浪费的地方 , 找出这个性能浪费的点 , 将其优化 , 就可以得到更好的算法 ;


如果一个字符串是回文子串 , 那么该字符串的 中心的 3 33 个字符肯定是回文串 , aba 形式的 ;


如 “mabcban” 字符串 , 如果已经检测到了 中间的 bcb 是回文串 , 再次扩大范围时 , 直接检测 “bcb” 两遍的单个字符是否一样即可 , 左右两遍各是一个 a , 一样 ;

完全没有必要再次监测 abcb , bcba 是否是字符串 , 这样就造成了性能上的浪费 ;



按照上述思想 , 可以进行如下设计 :

中轴线 : 回文串的关键在于其 " 中轴线 " , 以中轴线为中心 , 遍历两边的字符串是否相等 ;


如 : “mabcban” 字符串中 , 回文子串是 “abcba” , 字符 c 是中轴线 , 从该中轴线触发 , 两侧的字符串都相等 ;

第一层遍历 : 先对字符串进行一次遍历 , 假设遍历的当前字符是中轴线 ,

第二层遍历 : 再次遍历 , 比较两侧的字符是否相等 , 如果相等 , 则说明是回文子串 , 逐步向外遍历 , 看回文子串的最大长度 ;


该思想是取每个中轴线向两侧尽可能取最长的回文子串 ;



外层遍历设计 :


回文串有两种情况 , 假如字符串有 n nn 个字符 ;


情况一 : “abcba” 奇数个字符组成 , 中心轴是字符 , 有 n nn 个需要遍历的中心线 ;

情况二 : “abba” 偶数个字符组成 , 中心轴是字符之间的间隔 , 有 n − 1 n-1n−1 个需要遍历的中心线 ;

情况一 很容易实现 , 遍历每个字符即可 , 然后比较字符两端的字符是否相等 , 逐步扩大范围 , 直到获得最长回文子串 ;


情况二 需要 设置两个指针 L 和 R , 分别指向中心轴两侧 , L 指向中心轴左侧 , R 指向中心轴右侧 , 比较指针指向的字符是否相等 , 如果相等 , 然后两个指针各往两边走 , 继续比较指向的字符是否相等 , 直至获取到最长的回文子串 ;




2、中心线枚举算法代码示例


代码示例 :


class Solution {
    /**
     * @param s: 输入字符串
     * @return: 返回最长回文子串
     */
    public String longestPalindrome(String s) {
        if (s == null) {
            return null;
        }
        String longest = "";
        for (int i = 0; i < s.length(); i ++) {
            // 回文子串字符个数是奇数个
            String oddPalindrome = getPalindrome(s, i, i);
            if (longest.length() < oddPalindrome.length()) {
                longest = oddPalindrome;
            }
            // 回文子串字符个数是偶数个
            String evenPalindrome = getPalindrome(s, i, i + 1);
            if (longest.length() < evenPalindrome.length()) {
                longest = evenPalindrome;
            }
        }
        return longest;
    }
    private String getPalindrome(String s, int left, int right) {
        /*
            left right 两个指针分别指向中心线两侧的元素索引
            如果回文子串有奇数个字符, 中心线是字符, left = right = 中心线索引
            如果回文子串有偶数个字符, 中心线是空隙, left + 1 = right
         */
        while(left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }
}
class Main {
    public static void main(String[] args) {
        String palindrome = new Solution().longestPalindrome("mabcban");
        System.out.println(palindrome);
    }
}


O ( n 2 ) O(n^2)O(n

2

) 时间复杂度算法 , 该算法可接受 ;


image.png

目录
打赏
0
0
0
0
39
分享
相关文章
|
5月前
|
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
3月前
|
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
117 1
两个字符串匹配出最长公共子序列算法
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
346 1
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
151 1
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
5月前
|
惊爆!KPM算法背后的秘密武器:一行代码揭秘字符串最小周期的终极奥义,让你秒变编程界周期大师!
【8月更文挑战第4天】字符串最小周期问题旨在找出字符串中最短重复子串的长度。KPM(实为KMP,Knuth-Morris-Pratt)算法,虽主要用于字符串匹配,但其生成的前缀函数(next数组)也可用于求解最小周期。核心思想是构建LPS数组,记录模式串中每个位置的最长相等前后缀长度。对于长度为n的字符串S,其最小周期T可通过公式ans = n - LPS[n-1]求得。通过分析周期字符串的特性,可证明该方法的有效性。提供的C++示例代码展示了如何计算给定字符串的最小周期,体现了KPM算法在解决此类问题上的高效性。
107 0
C++ bcrypt算法 字符串加密,亲测有效
C++ bcrypt算法 字符串加密,亲测有效
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
KMP算法详解及其在字符串匹配中的应用
KMP算法详解及其在字符串匹配中的应用
程序员必知:《程序设计与算法(二)算法基础》《第一周枚举》熄灯问题POJ
程序员必知:《程序设计与算法(二)算法基础》《第一周枚举》熄灯问题POJ
41 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等