首页 > 代码库 > Leetcode5:Longest Palindromic Substring@Python
Leetcode5:Longest Palindromic Substring@Python
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example:
Input: "cbbd" Output: "bb"
动态规划法:以"ababae"为例:
1 class Solution(object): 2 def longestPalindrome(self, s): 3 """ 4 :type s: str 5 :rtype: str 6 """ 7 sLength=len(s) 8 begin=0 9 length=0 10 table=[] 11 for i in range(sLength): 12 tem=[] 13 for j in range(sLength): 14 tem.append(0) 15 table.append(tem) 16 17 for i in range(sLength): 18 table[i][i]=1 19 20 for i in range(sLength-1): 21 if s[i]==s[i+1]: 22 table[i][i+1]=1 23 begin=i 24 length=1 25 26 for tem in range(1,sLength): 27 for i in range(sLength-tem): 28 j=i+tem 29 if (s[i]==s[j] and table[i+1][j-1])==1: 30 table[i][j]=1 31 length=tem 32 begin=i 33 34 return s[begin:begin+length+1]
Leetcode5:Longest Palindromic Substring@Python
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。