1 minggu, 4 hari yang lalu - macroblocks
· 0
menit baca
LeetCode 5 - Longest Palindromic Substring
Topics: 💻 cs🏷️ problem📚 leetcode📄 medium
LeetCode Link: longest palindromic substringwriteup
Intuition
Instead of checking if every substring is a palindrome (which requires checking each character), we can observe that palindromes expand symmetrically from their center. For any palindrome, if we start from the middle and expand outward, the characters on both sides will match.
Approach
1. For each possible center position in the string, expand outward while characters match
2. Track the longest palindrome found during all expansions
3. Handle both odd-length palindromes (single character center) and even-length palindromes (two character center) by expanding from each position twice
4. Return the substring corresponding to the longest palindrome discovered
Complexity
Time complexity: O(n2) - we check 2n-1 centers, and each expansion can take up to O(n) time in the worst case (e.g., a string of all same characters)
Space complexity: O(1) - we only store indices and the result substring, no additional data structures needed
Solution
1. Brute Force O(n3)
class Solution:
def longestPalindrome(self, s: str) → str:
if len(s) < 2 or len(set(s)) == 1: # 1 or fewer is always a palindrome
return s
max_palindrome_len: int = 0
max_palindrome_substring: str = ""
len_s: int = len(s)
def is_palindrome(string_to_test: str) → bool: # abc
len_string = len(string_to_test)
for i in range(len_string // 2):
if string_to_test[i] ≠ string_to_test[len_string - i - 1]:
return False
return True
for i in range(len_s):
starting_char_in_s: str = s[i]
for j in range(i, len_s):
substring_to_test: str = s[i:j+1]
substring_to_test_len = len(substring_to_test)
if substring_to_test_len > max_palindrome_len:
if is_palindrome(substring_to_test):
max_palindrome_len = substring_to_test_len
max_palindrome_substring = substring_to_test
return max_palindrome_substring
2. Optimised O(n2)
class Solution:
def longestPalindrome(self, s: str) → str:
len_s: int = len(s)
if len_s < 2 or len(set(s)) == 1:
return s
def expand_palindrome(i: int) → str:
previous_index: int = i - 1
next_index: int = i + 1
while previous_index ≥ 0 and next_index ≤ len_s - 1:
previous_char: str = s[previous_index]
next_char: str = s[next_index]
if previous_char == next_char:
previous_index -= 1
next_index += 1
else:
break
max_odd_palindrome: str = s[previous_index + 1:next_index]
current_index: int = i
next_index: int = i + 1
while current_index ≥ 0 and next_index ≤ len_s - 1:
current_char: str = s[current_index]
next_char: str = s[next_index]
if current_char == next_char:
current_index -= 1
next_index += 1
else:
break
max_even_palindrome: str = s[current_index + 1: next_index]
if len(max_odd_palindrome) > len(max_even_palindrome):
return max_odd_palindrome
return max_even_palindrome
max_palindrome_len: int = 0
max_palindrome_string: str = ""
for index_to_test in range(len_s): # 0(n)
max_palindrome_at_index: str = expand_palindrome(index_to_test) # O(n)
len_max_palindrome_at_index: int = len(max_palindrome_at_index)
if len_max_palindrome_at_index > max_palindrome_len:
max_palindrome_len = len_max_palindrome_at_index
max_palindrome_string = max_palindrome_at_index
return max_palindrome_string
0
0
19
balas pos