문제 설명
https://leetcode.com/problems/longest-palindromic-substring
palindrom 이란 abc, aabaa, 우영우(?) 처럼 앞에서 읽으나 뒤에서 부터 읽으나 똑같은 문자열을 말한다. panlindrom을 찾으려니 세가지 케이스가 나왔다.
Palindrom 찾기
- Case 1. 중심 문자 기준으로 양옆 문자들이 같을때
- aba, aabaa …
- Case 2. 대칭일때
- aabb, abcdbcba
- Case 3. 두가지 모두 나올때
- aaaaaaaa
- -> Case 3 인 경우 Case 1 방법 계산으로 했을때 Case2 방법으로 했을때 둘 중 큰 값으로 함
순차적으로 index를 높혀가면서 위 케이스에 해당하는 panlindrom을 찾아나가는 방법으로 코드를 구현했다.
풀이
참고로 아래 코드는 정답 Pass 를 목적으로만 작성되어 깔끔하지는 않은 코드다. 그래도 시간복잡도 면에서는 꽤 높은 등수를 기록했다. Runtime: 256 ms, faster than 94.86%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution:
def longestPalindrome(self, s: str) -> str:
def get_palindrome_len(index: int, mid_index: bool):
# Case 1. index가 중심이 되어 양옆으로 character들이 같을때
if mid_index:
diff = 1
while(index - diff >= 0 and index + diff < len(s) and s[index - diff] == s[index + diff]):
#print(f"{s[index - diff]} and {s[index + diff]} same")
diff += 1
return diff -1
# Case 2. index와 index+1 값이 같고 양옆으로 character들이 같을때
else:
diff = 1
while(index - diff >= 0 and index+diff+1 < len(s) and s[index - diff] == s[index + diff + 1]):
diff += 1
return diff
# 길이 1인거 들어오면 바로 리턴
if len(s) == 1:
return s
# 2인거도 서로 같으면 리턴
elif len(s) == 2:
if s[0] == s[1]:
return s
else:
return s[0]
# 모든 문자열 같으면 리턴
all_same = True
for i in range(1,len(s)):
if s[i-1] != s[i]:
all_same = False
if all_same:
return s
# index 1부터 검사할거라 아래 처리
if s[0] == s[1]:
max_len = 2
max_str = s[:2]
else:
max_len = 1
max_str = s[0]
index = 1
while ( index < len(s) ):
diff_index = 1
return_str = ""
if index + 1 >= len(s):
break
if s[index] == s[index + 1] and s[index - 1] == s[index + 1]:
mid_diff_index = get_palindrome_len(index, mid_index=True)
not_mid_diff_index = get_palindrome_len(index, mid_index=False)
if mid_diff_index > not_mid_diff_index:
diff_index = mid_diff_index
return_str = s[index - diff_index : index + diff_index + 1]
else:
diff_index = not_mid_diff_index
return_str = s[index - diff_index + 1: index + diff_index + 1]
elif s[index] == s[index + 1]:
diff_index = get_palindrome_len(index, mid_index=False)
return_str = s[index - diff_index + 1: index + diff_index + 1]
elif s[index - 1] == s[index + 1]:
#print(f"{s[index - 1]} { s[index + 1]}" )
diff_index = get_palindrome_len(index, mid_index=True)
return_str = s[index - diff_index : index + diff_index + 1]
else:
return_str = s[index]
diff_index = 1
if len(return_str) > len(max_str) :
max_str = return_str
index += 1
return max_str
다른 풀이 `파이썬 알고리즘 인터뷰’의 풀이는 정말 매우 깔끔하다. 위코드는 지금 내가 봐도 이해못할 코드 ㅠㅠ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def longestPalindrome(s: str) -> str:
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]
if len(s) < 2 or s == s[::-1]:
return s
result = ''
for i in range(len(s) - 1):
result = max(result, expand(i, i +1), expand(i, i+2), key=len)
return result