最长回文子串
最长 回文 子串
2023-09-11 14:17:14 时间
# 给你一个字符串 s,找到 s 中最长的回文子串。
#
#
#
# 示例 1:
#
#
# 输入:s = "babad"
# 输出:"bab"
# 解释:"aba" 同样是符合题意的答案。
方法一:动态规划
# leetcode submit region begin(Prohibit modification and deletion) class Solution: def longestPalindrome(self, s: str) -> str: # https://www.jianshu.com/p/6f226c9180e2 dp = [[False]*len(s) for _ in range(len(s))] # 初始状态二维数组 max_start, max_len = 0, 0 for j in range(len(s)): # 右指针先走 for i in range(j+1): # 左指针跟随 if j-i < 2: dp[i][j] = (s[i]==s[j]) # 最多相差一个元素 else: dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1] # 两端字符相等,中间也为回文子串 # 记录索引值 cur_len = j-i+1 if dp[i][j] and max_len<cur_len: max_len = cur_len max_start = i return s[max_start:max_start+max_len] # leetcode submit region end(Prohibit modification and deletion)
相关文章
- 【BZOJ2565】最长双回文串(回文树)
- 【华为OD机试真题 python】最长的指定瑕疵度的元音子串 【2022 Q4 | 200分】
- 【算法】【字符串模块】判断括号字符串是否有效,如果无效则求最长的有效长度
- 华为python机试题目:整数与IP地址间的转换、图片整理、字串的连接最长路径查找、提取不重复的整数、字符串合并处理、字符串最后一个单词的长度、删除字符串中出现次数最少的字符
- 1040 Longest Symmetric String (25 分)【难度: 一般 / 知识点: 最长回文子串】
- [算法]死磕最长回文子串
- 求字符串列表中最长公子串
- [模板题][双指针]最长连续不重复子序列
- 力扣解法汇总1048. 最长字符串链
- LeetCode 5. 最长回文子串
- 【POJ 2250】Compromise(最长公共子序列LCS)
- 176、【动态规划】leetcode ——1143. 最长公共子序列(C++版本)
- POJ 1743 Musical Theme 后缀数组 不可重叠最长反复子串
- [LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子串
- 【bzoj2565】最长双回文串 Manacher+树状数组
- leetcode 409 Longest Palindrome 最长回文串(简单)