[LeetCode 풀이/python] 214. Shortest Palindrome (hard)

문제 설명: 문자열 s 가 주어졌을 때, 해당 문자열 앞에 적절한 문자를 추가함으로써 s 를 회문(palindrome) 으로 변환할 수 있다. 이러한 변환 과정을 수행하여 얻을 수 있는 가장 짧은 회문을 리턴하시오.

 

(You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.)

 

 

예시 1)

입력: s = "aacecaaa"  --> 출력: "aaacecaaa"

 

예시 2)

입력: s = "abcd"  -->  출력: "dcbabcd"

 

 

제한 조건:

• 0 <= s.length <= 5*10^4
• s 는 영문 소문자만을 포함함

 

------ * ------ * ------ * ------

 

[풀이 1안]  (not a solution...!)

• 접근법
  • 문자열 s 를 배열로 변환하여 탐색을 진행하며 '앞에서부터 i 번째 문자와 뒤에서부터 i 번째 문자가 동일한 경우' 해당 부분 문자열(substring) s[i : -i] 이 회문(palindrome) 인지 체크 
    • 애초에 substring s[i] 와 s[-(i+1)] 이 같지 않거나 같더라도 회문이 아닌 경우(else 조건), s[-(i+1)] 에 해당하는 문자를 s 의 앞에 추가해주어야 회문을 만들 수 있으므로, 해당 문자를 별도 배열에 저장함 
    • substring 이 회문인 경우 탐색 중단하고 빠져나옴
  • 회문을 발견하여 for loop 를 통한 탐색이 끝나면 지금까지 배열 add 에 누적된 문자들을 기존 s 앞에 concat 함으로써 가장 짧은 회문을 만들어낼 수 있음
    • 배열 add 에 원소가 추가되는 순서는 s 의 맨 끝에서부터 이므로, stack 형식의 배열에 차례로 문자를 추가하고 그대로 s 앞에 연결해주면 됨!

 

• 코드 구현

def shortestPalindrome(s: str) -> str:
    add = []
    tmp_s = list(s)
        
    for i in range(len(s)):
        if (s[0] == s[-(i+1)]) and (check_palindrome(''.join(tmp_s))):
            break
        else:
            a = tmp_s.pop()
            add.append(a)
    
    add_str = ''.join(add)
    return add_str + s
    
def check_palindrome(s):
    max_len = len(s)//2
    for i in range(max_len):
        if s[i] != s[-(i+1)]:
            return False
    return True
    

 

• 결과
  • 아이디어 자체는 틀리지 않은 것으로 보이나 전체 s 길이를 탐색하는 데에 O(n) * 회문 체크에 O(n/2) = O(n^2) 가 되어 효율성 문제가... 결국 TimeLimitExceedError...!! ㅠ_ㅠ

 

 

[풀이 2안]  (w/ solution peeping)

• 접근법
  • 문자열(string) 타입에 대해 사용 가능한 파이썬 내장 함수 중 startswith() 를 이용하는 방법
    • str.startswith(value, start, end) 메소드는 문자열 str 가 특정 문자열 value 로 시작하면 True 를, 아니면 False 를 리턴
    •  start, end 는 문자열의 특정 위치에서부터 탐색을 시작할 / 끝내고자 할 때 범위를 지정하기 위해 사용할 수 있는 Optional parameter 
  • 원본 문자열 s 를 거꾸로 뒤집은 문자열 r 을 만들어, r 의 substring r[i:] 가 s 의 시작 부분과 같은지 체크
  • True 인 경우 s 는 회문에 해당하는 r[i:] + alpha 로 구성되어 있다고 할 수 있고, alpha 에 해당하는 r[:i] 을 s 의 앞에 concat 함으로써 (alpha + panlindrome + alpha) 전체가 회문인 문자열을 만들어 낼 수 있음!

 

• 코드 구현

def shortestPalindrome(s: str) -> str:
    r = s[::-1]
    for i in range(len(s)+1):
        if s.startswith(r[i:]):
            #print(r[:i])
            return r[:i] + s
            

 

• 결과
  • 회문(palindrome) 여부를 확인하는 훌륭한 접근법을 알게 되었다... 뿌_듯
  • startswith() 메소드가 단순히 문자열 s 를 슬라이싱해서 비교하는 방식이라면, O(n + (n-1) + ... + 1) = O(n^2) 이므로 총 O(n^3) 이 되어 효율성 통과를 못할텐데, 훨씬 빠른걸 보면 다른 방식으로 구현되어 있는가 봉가...
    (왜 해당 함수 Time Complexity 를 못찾겠지... ㅠ_ㅠ)