•
문제 설명 : 제공된 문자열 목록 중, 처음 등장하는 순회 문자열(뒤집어도 동일한 문자열)을 반환, 없다면 "" 반환
•
풀이 방법
◦
단어의 중간 지점을 구하여 앞, 뒤를 비교하는 방식
◦
다만, 단어의 길이가 홀수일 때 / 짝수일 때 Slice하는 위치가 달라야하기 때문에 나머지(mod) 값을 활용
•
시간복잡도 :
•
성공 코드
from typing import List
# O(N^2)
class Solution:
def firstPalindrome(self, words: List[str]) -> str:
# 최악의 경우 모든 단어를 확인하기 때문에 O(N)
for word in words:
mid, mod = divmod(len(word), 2)
# 단어의 길이가 홀수일 경우, 중간 문자를 제외하고 비교
# list() 형변환은 문자열의 데이터를 사용하여 새로운 리스트를 만들기 때문에 -> O(N)
# list[:mid]는 Slice 구문으로, O(mid) -> O(N)
# list[mid + mod:]는 Slice 구문으로, O(mid + mod) -> O(N)
# list[::-1] 는 Reverse 구문으로 기존 리스트 데이터를 역순으로 배치한 새로운 리스트를 반환, O(N)
# O(N + mid) + O(N + mid + mod + N) -> O(N)
if list(word)[:mid] == list(word)[mid + mod :][::-1]:
return word
return ""
Python
복사