5. Longest Palindromic Substring [Strings, dynamic programming]

Problems:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

 

Example 1:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

 

Example 2:

Input: "cbbd"

Output: "bb"

 

-Summary-

Approach: Expand around the center

1. Two cases exist.

- Palindrome with odd lengths of string (example: 'aba', 'abcba') --> where 1 character in the middle is unique.

- Palindrome with even lengths of string (example: 'abba', 'abccba')  --> where two characters in the middle are same.

2. - For the odd case, we set left and right index in the same position and keep expanding its index until the left and right character does not match.

   - For the even case, we add 1 more position to the right index to check if two characters are the same in the middle and keep expanding its index until the left and right character does not match.

3. return with the longest left and right index of the string.

Time Complexity: O(n^2)

--> We used '2n' operation in the first for loop. and 'n' operation for the 'longestAtIndex' method. (2n*n = 2n^2 = n^2)

Space Complexity: O(1)

--> Didn't use any data structures.

 

-Without using dynamic programming-

Make a two-pointer and sliding-window of strings with len 2 and len 3.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2 or s == s[::-1]:
            return s
        
        def expand(left,right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]
        
        res = ''
        
        for i in range(len(s)-1):
            res = max(res, expand(i,i+1), expand(i,i+2), key=len)
            
        return res

 

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]