✓[LeetCode] 5. Longest Palindromic Substring

 Given a string s, return the longest palindromic substring in s.

 

Constraints:

  ▷ 1 <= s.length <= 1000

  ▷ s consist of only digits and English letters.

 

Example:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

 

 문자열 시작 알파벳 위치를 한 칸씩 옮겨가며 더해 가장 큰 팰린드롬을 찾는다는 로직을 생각했다. 문자열이 알파벳 한 개인 경우까지 고려했다. 리트코드에서 실행은 됐지만, 계속 시간초과가 발생하였다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        if len(s) == 1:
            return s
        
        pd_list = []
        
        # check substrings whether Palindrome or not using indices and nested roof
        for i in range(0, len(s)-1):
        
        # every nested roof, end point has to be decline!
            for j in range(0, len(s)-i):
                temp = s[i:i+j+1]
                if temp == temp[::-1]:
                    pd_list.append(temp)

        # below sentence(line 16) causes Runtime Error "max() arg is an empty sequence"
        return max(pd_list, key=len)

 

 그래서 또 풀이를 봤다.. 하루 이상 고민하는 것보다는 지금은 일정 시간 고민 후에도 풀지 못한다면 풀이를 보고 배우는 단계라고 생각한다. 이 문제는 다이나믹 프로그래밍을 이용한 풀이는 직관적 이해가 어렵고 실행 속도가 늦다고 한다. 4년전 배운게 조금 떠오른다. 이 문제는 팰린드롬 판별만 하면 된다는 점에 착안해서, 매칭이 될 때 중앙을 중심으로 점점 확장해 나가면서 가장 긴 팰린드롬을 판별하는 알고리즘을 구현해야 한다고 한다. 아직은 스스로 이 정도 코드까지 작성하긴 어려울 것 같다.. 하지만 포인터를 이용하자는 아이디어를 얻었다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        # two-pointer expansion function
        def expand(left: int, right: int) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]
        
        # return if there are no options
        if len(s) < 2 or s == s[::-1]:
            return s
        
        result = ''
        
        # move sliding window to right
        for i in range(len(s) - 1):
            result = max(result,
                            expand(i, i + 1),
                            expand(i, i + 2),
                            key=len)
        
        return result