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 条评论

发表回复

Avatar placeholder

您的邮箱地址不会被公开。 必填项已用 * 标注