首页 > 其他分享 >5_最长回文子串

5_最长回文子串

时间:2024-08-30 17:04:56浏览次数:13  
标签:子串 begin len maxLen 最长 dp 回文

5_最长回文子串

【问题描述】

给你一个字符串 s,找到 s 中最长的回文子串。

示例:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

【算法设计思想】

本题主要使用到了动态规划的算法思想。其程序的大致执行过程如下:
首先,我们先求取下该字符串的长度,然后判断下这个字符串的长度是否为0或者1,如果是0或者1,则直接返回即可。如果不是,则我们让子串的长度从2开始,我们逐个遍历字符串即可。
在此,我们先默认设计下几个参数:
maxLen,即最长回文子串的长度。
begin,即最长回文子串的左索引。
dp,即用来记录存储结果一个二维数组。每个单独的字符串我们都可以看作是一个回文子串,故我们初始化其对角线上的元素为true。

接下来正式进入本算法的核心过程,先从L=2开始逐个遍历,然后在循环内部,i代表左索引,j代表右索引,然后判断下s[i]和s[j]是否相等,如果不相等则说明是一个长度为2的回文子串,设置为false;如果不相等,则再判断下j - i(即子串的长度L)是否小于3,如果小于3则设置dp为true,如果大于3,则利用到对应的状态转移方程,我们判断其子串即可。

最后判断更新下maxLen和begin的值,返回子串。

【算法描述】

C++:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        vector<vector<int>> dp(n, vector<int>(n));
        // 初始化:所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= n; L++) {
            // 枚举左边界,左边界的上限设置可以宽松一些
            for (int i = 0; i < n; i++) {
                // 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界,就可以退出当前循环
                if (j >= n) {
                    break;
                }

                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};


Java:

public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化:所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界,左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界,就可以退出当前循环
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}


Python:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        
        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        
        # 递推开始
        # 先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界,左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界,就可以退出当前循环
                if j >= n:
                    break
                    
                if s[i] != s[j]:
                    dp[i][j] = False 
                else:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                
                # 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]

标签:子串,begin,len,maxLen,最长,dp,回文
From: https://www.cnblogs.com/zeta186012/p/18389090

相关文章

  • leetcode_128_最长连续序列解析
    题目给定一个未排序的整数数组nums,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。示例1:输入:nums=[100,4,200,1,3,2]输出:4解释:最长数字连续序列是[1,2,3,4]。它的长度为4。示例2:输入......
  • 代码随想录day44 || 1143 最长公共子序列, 1035 不相交的线, 53 最大子序列和, 392 判
    1143最长公共子序列funclongestCommonSubsequence(text1string,text2string)int{ //思路和判断最长公共数组一样 //dp[i][j]表示以text1[i],text2[j]为结尾的最长公共子序列的长度 //iftext1[i]==text2[j]{dp[i+1][j+1]=dp[i][j]+1}else{dp[i+1][j+1]=......
  • 代码随想录算法训练营第四十三天 | 300.最长递增子序列 , 674. 最长连续递增序列 , 718.
    目录300.最长递增子序列 思路1.dp[i]的定义2.状态转移方程3.dp[i]的初始化4.确定遍历顺序 5.举例推导dp数组方法一:动态规划方法二:贪心心得收获 674.最长连续递增序列思路动态规划1.确定dp数组(dptable)以及下标的含义2.确定递推公式3.dp数组如何初始化4.......
  • LCR 018. 验证回文串【简单】
    题目描述给定一个字符串s,验证s是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。本题中,将空字符串定义为有效的回文串。示例1:输入:s=“Aman,aplan,acanal:Panama”输出:true解释:“amanaplanacanalpanama”是回文串示例2:输入:s=“r......
  • 代码随想录day43 || 300 最长递增子序列,674 最长连续递增子序列,718 最长重复子数组
    300最长递增子序列varpath[]intvarresintfunclengthOfLIS(nums[]int)int{ //尝试回溯思路 iflen(nums)==1{ return1 } path=[]int{} res=0 backtracking(nums) returnres}funcbacktracking(nums[]int){ iflen(nums)==0{ iflen(pat......
  • 234. 回文链表
    回文链表传送锚点:234.回文链表-力扣(LeetCode)给你一个单链表的头节点head,请你判断该链表是否为回文链表。如果是,返回true;否则,返回false。示例1:输入:head=[1,2,2,1]输出:true示例2:输入:head=[1,2]输出:false提示:链表中节点数目在范围[1,105]内0<=......
  • 【数据结构-前缀异或和】力扣1177. 构建回文串检测
    给你一个字符串s,请你对s的子串进行检测。每次检测,待检子串都可以表示为queries[i]=[left,right,k]。我们可以重新排列子串s[left],…,s[right],并从中选择最多k项替换成任何小写英文字母。如果在上述检测过程中,子串可以变成回文形式的字符串,那么检测结果为......
  • 回文自动机小记
    构建口胡一下过程:\(fail\)边指向自己的最长回文后缀(偶根指向奇根)。定理:每添加一个字符,至多新增一个新的本质不同的回文串,且是所有回后缀中最长的。由此得出推论:本质不同的回文子串(回文自动机的点数)不超过|S|暴力跳终止链,找到第一个左侧有\(x\)的回文后缀\(v\)。......
  • tips in windows/ 1.windows文件路径最长限制
    1.windows文件路径最长限制场景:在用文件资源管理器删除名称超过255字符的文件(文件名最大字符限制就是255)时,发现删除不了,也没反应原因:windows删除调用的是explorer,对路径限制不能超过260,此时超过了,但又由于是应用层,所以不会直接给以报错。使用杀毒软件可以是因为他们调用的是......
  • 秋招突击——8/22——算法整理——滑动窗口类型题目思维方式——查找最短包含子串、找
    文章目录引言正文基本思路查找最短包含子串考试实现代码考试反思代码===》先确定一边的指针,然后再移动另外一个指针修改找到字符串中所有字母异位词复习实现参考实现无重复最长子串个人实现总结引言今天面试字节,被老师指出来代码能力薄弱,确实如此。后续应当多加......