[리트코드/파이썬] 5. Longest Palindromic Substring

 

[리트코드/파이썬] 5. Longest Palindromic Substring

5. Longest Palindromic Substring

Medium

Given a string s, return the longest

palindromic

substring

in

s

 

참고

palindromic 문자열:
왼쪽에서 오른쪽으로 읽으나 오른쪽에서 왼쪽으로 읽으나 같은 문자열을 말한다.

 

Example 1:

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

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Accepted

2.8M

Submissions

8.3M

Acceptance Rate

33.3%

---

[내 풀이]

※ 소요시간 : 1시간

※ 풀이 전략

- 대칭인 경우는 대칭의 중심이 홀수인 케이스 A, 짝수인 케이스B 로 나뉜다. 

- 모든 가능한 대칭의 중심 (0~n-1)에 대하여 그 인덱스에서의 문자열 길이(i에 대한 length)를 계산하고, 최대 길이(e-s+1)를 찾아 st[s:e+1] 을 반환한다. 

class Solution:
    def longestPalindrome(self, st: str) -> str:
        n = len(st)
        def check(l, s, e):
            if s>=0 and e<=n-1 and st[s]==st[e]:
                while s-1>=0 and e+1<=n-1 and st[s-1]==st[e+1]:
                    s = s-1
                    e = e+1
                    l += 2 
                return l
            return 0
        # 중심 인덱스 기준
        s = 0
        e = 0
        for i in range(n):
            lengthA = check(1, i, i)
            lengthB = check(2, i, i+1)
            length = max(lengthA, lengthB)
            if length > e-s:
                s = i - (length-1)//2 
                e = i + (length)//2 
        return st[s:e+1]

 

※ 중요 포인트

- 이런 극단적인 케이스를 먼저 고려하고, 시간 복잡도를 계산한다. 

- 풀이 근거: 최대 n은 1000이므로, i가 500즈음일 때 check( )함수의 while문이 최대 500번 돌게 된다. 

- 즉 최악의 경우 1000*500*2 = 10^6인데, 최악인 케이스에서 while문의 n=500이고 그 전후로는 500미만이므로 10^6을 무조건 넘지 않는다. 따라서 1초 안에 통과할 수 있을 것이라 생각했다.  

 

---

[다른 사람의 풀이]

※ 풀이 전략

- 모든 i부터 j까지 s[i:j] 를 확인하되

- 탐색 순서를 변경하고 (i는 작을 수록, j는 클 수록 큰 long을 구할 확률이 높음) 

- max값인 len(long) 보다 작은 경우를 cut하여 걸리는 시간을 최소화한 방법.

- 결국은 n^2 이고, 더 짧은 풀이이긴 하지만 시간 효율은 좋지 않다. 

class Solution(object):
    def longestPalindrome(self, s):
        long = ""
        for i in range(len(s)):
            for j in range(len(s), i, -1):
                if len(long) >= j-i:
                    continue
                elif s[i:j] == s[i:j][::-1]:
                    long = s[i:j]
        return long

 

 

---

- 위의 다른 분의 풀이를 읽고 보니 굳이 continue 일 필요가 없고 break이면 의미 없는 루프를 더 빨리 벗어날 수 있으니 break으로 하면 아주 조금이지만 시간을 줄일 수 있다. (이정도론 3%밖에 못 제치는구나.)

class Solution(object):
    def longestPalindrome(self, s):
        long = ""
        for i in range(len(s)):
            for j in range(len(s), i, -1):
                if len(long) >= j-i:
                    break
                elif s[i:j] == s[i:j][::-1]:
                    long = s[i:j]
        return long