https://leetcode-cn.com/problems/longest-palindromic-substring
代码:
# -*- coding:utf-8 -*- class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ # 左右走的长度 flag = 0 # 回文字开始位置 start = 0 for i in range(len(s)): # 以当前位置为中心,左右各扩充1位 if i - flag >= 1 and s[i - flag - 1:i + 2] == s[i - flag - 1:i + 2][::-1]: start = i - flag - 1 flag += 2 continue # 以当前位置为准,向右扩充一位 if i - flag >= 0 and s[i - flag:i + 2] == s[i - flag:i + 2][::-1]: start = i - flag flag += 1 return s[start:start + flag + 1] if __name__ == '__main__': # s = 'ccc' # s = 'babab' s = 'ababd' print(Solution().longestPalindrome(s))
思路:采用贪心的思想,从第一个元素出发,先向左一位,向右一位查看两个是否相等,如果相等那么说明回文字长度可以+2,如果不相等,则向右一位判断是否和当前位置相等(这里优先选择了较长的+2,如果满足则不进行向右一位判断)。
每进行一次迭代都选择当前索引下最优的选择,即左右选择或者右选择。
0 条评论