리트코드 코딩 테스트 준비
https://leetcode.com/problems/longest-palindromic-substring/
문제에 대한 자세한 설명은 다음 사이트에서 확인 할 수 있다.
Given a string s, return the longest palindromic substring in s.
문자열의 값을 계속 비교해나가면서 거꾸로 뒤집은 문자열과 길이가 같을때 max_length값 보다 크면 계속 업데이트 해주면서 가장 긴 문자 를 찾는다.
class Solution:
def longestPalindrome(self, s: str) -> str:
a = Counter(s)
sub_str = ""
flag = 1
answer = ""
for i in range(len(a)) :
if a[i] != 1 :
flag = 0
break
if flag == 1 :
return 1
else :
for i in range(len(s)) :
sub_str = ""
for j in s[i:] :
sub_str = sub_str + j
if sub_str == sub_str[::-1] and len(answer) < len(sub_str) :
answer = sub_str
return answer
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
maxLen = 0
ans = ""
for i in range(n):
# 길이가 홀수인 palindrome 조사
left, right = i, i
while True:
if (left >= 0 and right < n) and s[left] == s[right]:
if maxLen < right - left + 1:
maxLen = right - left + 1
ans = s[left:right+1]
left -= 1
right += 1
else:
break
# 길이가 짝수인 palindrome 조사
left, right = i, i+1
while True:
if (left >= 0 and right < n) and s[left] == s[right]:
if maxLen < right - left + 1:
maxLen = right - left + 1
ans = s[left:right+1]
left -= 1
right += 1
else:
break
return ans
내가 푼 코드는 시간제한이 걸렸다. 큰 인풋 값을 넣으면 O(n2)로는 무리인거 같다.
다른사람이 풀이한 코드를 보면서 작성하였다.
다시 풀어봐야겠다..