shuuji3.xyz
[READ-ONLY] Mirror of https://github.com/shuuji3/leetcode. 馃搩 Code submitted to LeetCode
leetcode.com/shuuji3/
leetcode
leetcode-solutions
1#
2# @lc app=leetcode id=5 lang=python3
3#
4# [5] Longest Palindromic Substring
5#
6# https://leetcode.com/problems/longest-palindromic-substring/description/
7#
8# algorithms
9# Medium (28.43%)
10# Total Accepted: 741.4K
11# Total Submissions: 2.6M
12# Testcase Example: '"babad"'
13#
14# Given a string s, find the longest palindromic substring in s. You may assume
15# that the maximum length of s is 1000.
16#
17# Example 1:
18#
19#
20# Input: "babad"
21# Output: "bab"
22# Note: "aba" is also a valid answer.
23#
24#
25# Example 2:
26#
27#
28# Input: "cbbd"
29# Output: "bb"
30#
31#
32#
33class Solution:
34 def longestPalindrome(self, s: str) -> str:
35 for substring in self.create_substrings(s):
36 if self.is_palindrome(substring):
37 return substring
38 return ''
39
40 def create_substrings(self, s: str):
41 length = len(s)
42 for substring_length in range(length, 0, -1): # [3, 2, 1] if s == 'aba'
43 i = 0
44 j = substring_length
45 while j < length + 1:
46 yield s[i:j]
47 i += 1
48 j += 1
49
50 def is_palindrome(self, substring: str) -> bool:
51 center_index = len(substring) // 2
52 first_part = substring[:center_index + 1] # 'abc' for 'abcde'
53 last_part = reversed(substring[center_index:]) # 'edc' for 'abcde'
54 for c1, c2 in zip(first_part, last_part):
55 if c1 != c2:
56 return False
57 return True