当前位置:网站首页>leetcode:5. Longest palindrome substring [DP + holding the tail of timeout]
leetcode:5. Longest palindrome substring [DP + holding the tail of timeout]
2022-07-07 02:24:00 【White speed Dragon King's review】
analysis
dp[i][j] Express i To j Whether palindrome
And the special case is dp[i][i] dp[i][i + 1]
Other dp[i][j] see dp[i + 1][j - 1] Value Whether it's not 0
as well as s[i] and s[j] Whether it is equal or not
ac code
class Solution:
def longestPalindrome(self, s: str) -> str:
# n * n
# dp[i][j] Express [i, j] Palindrome length of
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
maxn = 1
ans = s[0]
for l in range(2, n + 1):
for start in range(n - l + 1):
#print(start, start + l - 1)
if l == 2:
if s[start] == s[start + 1]:
dp[start][start + 1] = 2
else:
dp[start][start + 1] = 0
else:
if s[start] == s[start + l - 1] and dp[start + 1][start + l - 2] > 0:
dp[start][start + l - 1] = dp[start + 1][start + l - 2] + 2
else:
dp[start][start + l - 1] = 0
if dp[start][start + l - 1] > maxn:
maxn = dp[start][start + l - 1]
ans = s[start: start + l]
#print(dp)
return ans
summary
A two-dimensional dp
follow-up Reverse greedy violence is faster ...
class Solution:
def longestPalindrome(self, s: str) -> str:
def check(s):
return s == s[::-1]
# n * n
# dp[i][j] Express [i, j] Palindrome length of
n = len(s)
maxn = 1
ans = s[0]
for l in range(n, 0, -1):
for start in range(n - l + 1):
if check(s[start: start + l]) and l > maxn:
maxn = l
ans = s[start: start + l]
return ans
#print(dp)
#return ans
return s[0]
边栏推荐
- 云原生混部最后一道防线:节点水位线设计
- 将截断字符串或二进制数据
- Dall-E Mini的Mega版本模型发布,已开放下载
- MFC Windows 程序设计[147]之ODBC数据库连接(附源码)
- Livox激光雷达硬件时间同步---PPS方法
- Command injection of cisp-pte
- 3D laser slam: time synchronization of livox lidar hardware
- Halcon knowledge: segment_ contours_ XLD operator
- postgresql之整体查询大致过程
- 3--新唐nuc980 kernel支持jffs2, Jffs2文件系统制作, 内核挂载jffs2, uboot网口设置,uboot支持tftp
猜你喜欢
3D laser slam: time synchronization of livox lidar hardware
Schedulx v1.4.0 and SaaS versions are released, and you can experience the advanced functions of cost reduction and efficiency increase for free!
人脸识别应用解析
Flir Blackfly S工业相机:颜色校正讲解及配置与代码设置方法
FLIR blackfly s usb3 industrial camera: white balance setting method
Several classes and functions that must be clarified when using Ceres to slam
Vingt - trois mille feuilles? "Yang mou" derrière l'explosion de la consommation végétale
Cat recycling bin
FLIR blackfly s industrial camera: configure multiple cameras for synchronous shooting
本周 火火火火 的开源项目!
随机推荐
How do I dump SoapClient requests for debugging- How to dump SoapClient request for debug?
纽约大学 CITIES 研究中心招聘理学硕士和博士后
MetaForce原力元宇宙开发搭建丨佛萨奇2.0系统开发
使用Ceres进行slam必须要弄清楚的几个类和函数
[C # notes] use file stream to copy files
Metaforce force meta universe development and construction - fossage 2.0 system development
Use of pgpool II and pgpooladmin
FLIR blackfly s industrial camera: configure multiple cameras for synchronous shooting
Flir Blackfly S 工业相机:配置多个摄像头进行同步拍摄
The GPG keys listed for the "MySQL 8.0 community server" repository are already ins
Jacob Steinhardt, assistant professor of UC Berkeley, predicts AI benchmark performance: AI has made faster progress in fields such as mathematics than expected, but the progress of robustness benchma
#夏日挑战赛#数据库学霸笔记(下)~
Tips for web development: skillfully use ThreadLocal to avoid layer by layer value transmission
3D激光SLAM:Livox激光雷达硬件时间同步
String or binary data will be truncated
Lombok同时使⽤@Data和@Builder 的坑
Web开发小妙招:巧用ThreadLocal规避层层传值
Collection recommandée!! Quel plug - in de gestion d'état flutter est le plus fort? Regardez le classement des manons de l'île, s'il vous plaît!
Web3的先锋兵:虚拟人
【论文阅读|深读】 GraphSAGE:Inductive Representation Learning on Large Graphs