【CT】LeetCode手撕—5. 最长回文子串

2024-06-14 13:04
文章标签 leetcode 最长 回文 子串 ct

本文主要是介绍【CT】LeetCode手撕—5. 最长回文子串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 题目
  • 1-思路
  • 2- 实现
    • ⭐5. 最长回文子串——题解思路
  • 3- ACM实现


题目

  • 原题连接:5. 最长回文子串

1-思路

  • 子串的定义:子串是原始字符串的一个连续部分
  • 子序列的定义:子序列是原始字符串的一个子集
  • 记录最长回文子串的起始位置以及其长度,最终通过下标截取

动规五部曲

  • 1.定义 dp 数组
    • boolean dp[i][j] 代表区间在 [i,j] 的子串是否是回文
  • 2.递推公式
    • nums[i] == nums[j] 的前提下
    • ① 当 j-1 - (i+1) +1 <2 时,也就是 区间严格小于 2 的时候 j-i<3dp[i+1][j-1] = true
    • ② 否则 dp[i][j] = dp[i+1][j-1]
  • 3.初始化
    • 单个字符一定是回文串dp[i][i] = true
  • 4. 遍历
    • 在得到一个 dp[i][j]true 时,就记录字符串的起始位置和长度
    • 由于 dp[i][j] 从左下角的位置推导来,因此遍历的方式以列遍历,先遍历列再遍历行
    • 由递推公式可以得到,dp[i][j] 由左下角的元素推导而来,因此 i 的遍历顺序是从 s.length() 开始遍历

2- 实现

⭐5. 最长回文子串——题解思路

在这里插入图片描述

class Solution {public String longestPalindrome(String s) {if(s.length()<2){return s;}int maxLen = 1;int begin = 0;//1. 定义 dp数组// dp[i][j] 代表区间[i,j]内的子串是否回文boolean[][] dp = new boolean[s.length()][s.length()];// 2.递推公式// if(s.charAt(i)==s.charAt(j)) {dp[i][j] = dp[i+1][j-1];}// 3.初始化// dp[i][i] = true;for(int i = 0 ; i < s.length();i++){dp[i][i] = true;}// 4.遍历顺序for(int i = s.length()-1 ; i >= 0 ;i--){for(int j = 0 ; j < s.length();j++ ){if(s.charAt(i) == s.charAt(j)){// 单个字符 没意义if(j-i<3){dp[i][j] = true;}else{dp[i][j] = dp[i+1][j-1];}}// 只要 dp[i][j] == true 成立,就表示 子串[i..j] 回文,此时记录长度和起始位置if(dp[i][j] && j-i+1>maxLen){maxLen = j-i+1;begin = i;}}}return s.substring(begin,begin+maxLen);}
}

3- ACM实现

public class maxPlaindrome {public static String maxPlaindrome(String str){int maxLen = 1;int begin = 0;int len = str.length();if(len<2){return str;}//1.定义dpboolean[][] dp = new boolean[len][len];//2.递推// if(s.charAt(i) == s.charAt(j)){ if(j-i>3){dp[i][j]=true;}else{dp[i][j] =dp[i+1][j-1];}}// 初始化for(int i = 0 ; i < len;i++){dp[i][i] = true;}// 4.遍历for(int i = len-1;i>=0;i--){for(int j = 1;j<len;j++){if(str.charAt(i) == str.charAt(j)){if(j-i<3){dp[i][j] = true;}else{dp[i][j] = dp[i+1][j-1];}}if(dp[i][j] && j-i+1>maxLen){maxLen = j-i+1;begin =i;}}}return str.substring(begin,begin+maxLen);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入字符串");String str = sc.nextLine();System.out.println("最长回文子串为"+maxPlaindrome(str));}
}

这篇关于【CT】LeetCode手撕—5. 最长回文子串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1060478

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已。 但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =)。小Ho手

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &