【LeetCode】0005最长回文字

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，如果满足则不进行向右一位判断）。

每进行一次迭代都选择当前索引下最优的选择，即左右选择或者右选择。