[leetcode algorithms]題目5

5. Longest Palindromic Substring

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"

自己寫的代碼：

遍歷字元串，從中間往兩邊查找，如果遇到字元不一致的情況則停止查找，跳入下一個字元串。運行時間1262 ms

class Solution: def longestPalindrome(self, s): """ :type s: str :rtype: str """ n = len(s) res = "" for i, char in enumerate(s): tmp1 = tmp2 = "" #odd left = right = i while 1: if left is -1 or right == n or s[left] is not s[right]: tmp1 = s[left+1:right] break else: left -= 1 right += 1 #even left = i right = i + 1 while 1: if left is -1 or right == n or s[left] is not s[right]: tmp2 = s[left+1:right] break else: left -= 1 right += 1 #compare odd and even str if len(tmp2) > len(tmp1): tmp = tmp2 else: tmp = tmp1 #compare res and tmp str if len(tmp) > len(res): res = tmp return res

受討論區啟發後寫的代碼：

其實思路是一樣的，但是用helper函數把代碼變得更加簡潔

class Solution: def longestPalindrome1(self, s): res = "" for i in range(len(s)): res = max(self.helper(s,i,i), self.helper(s,i,i+1), res, key=len) return res def helper(self,s,l,r): while 0<=l and r < len(s) and s[l]==s[r]: l-=1; r+=1 return s[l+1:r]

推薦閱讀：