https://github.com/onlybooks/algorithm-interview
1. 문제
5. Longest Palindromic Substring
가장 긴 팰린드롬 부분 문자열을 출력하라
팰린드롬: 뒤집어도 같은 내용인 것 ex) "aba", "aaaaa"
2. 내 풀이
def longestPalindrome(self, s: str) -> str:
for i in range(len(s)):
for j in range(i + 1):
temp = s[j:len(s) - i + j]
if temp == temp[::-1]:
return temp
Brute Force 방식을 사용해서 가능한 모든 부분 문자열을 선택하고, 선택한 부분이 팰린드롬인지 확인했다. 그리고 가장 긴 팰린드롬을 찾아야 하기 때문에 부분 문자열 중에서는 길이가 긴 것을 먼저 선택했다. 시간복잡도는 O(n^3)이다.
3. 중앙을 중심으로 확장하는 방법
def longestPalindrome(self, 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
이 풀이 방법은 포인터를 이용해서 문자열을 처음부터 끝까지 탐색한다. 그리고 두개 혹은 세개의 문자로 이루어진 팰린드롬이 발견된다면 해당 팰린드롬의 앞, 뒤 문자를 하나씩 확인하면서 최장 팰린드롬을 찾는다. O(n^2)의 시간복잡도를 가진다.
4. Dynamic Programing(동적 프로그래밍)을 이용한 방법
동적 프로그래밍이란 큰 문제를 여러개의 작은 문제로 나누어서 해결하고, 작은 문제를 풀었던 값을 저장해두고 재사용하는 방법이다. 지난 포스팅에서 다루었던 피보나치 수열을 O(n)의 시간복잡도로 구하는 방법도 동적 프로그래밍의 한 종류이다.
https://baechu-story.tistory.com/9?category=991646
"bab"라는 문자열이 팰린드롬이고, 이 문자열에 양쪽에 "a"가 추가되어 만들어진 "ababa"도 팰린드롬이다. 이 문제를 풀 때는 이처럼 팰린드롬 양쪽에 같은 문자가 추가되면 그 역시도 팰린드롬이라는 점을 이용한다. 먼저 모든 경우의 수로 부분 문자열을 만들어 각 문자열이 팰린드롬인지 확인한다. 이 과정에서 해당 문자열이 팰린드롬인지 여부를 배열에 저장하고, 길이가 4 이상인 문자열이 나타나면 양쪽 끝 문자가 같은지, 양쪽 끝을 제외한 문자가 팰린드롬인지를 배열에서 확인한다. 이 두가지 조건이 맞다면 해당 문자열을 팰린드롬이라고 판단하고 배열에 저장한다. 이 방법은 O(n^2)의 시간복잡도를 가진다.
/* 자바를 이용한 풀이 */
public String longestPalindrome(String s) {
if (s == null || "".equals(s)) {
return s;
}
int len = s.length();
String ans = "";
int max = 0;
boolean[][] dp = new boolean[len][len];
for (int j = 0; j < len; j++) {
for (int i = 0; i <= j; i++) {
boolean judge = s.charAt(i) == s.charAt(j);
dp[i][j] = j - i > 2 ? dp[i + 1][j - 1] && judge : judge;
if (dp[i][j] && j - i + 1 > max) {
max = j - i + 1;
ans = s.substring(i, j + 1);
}
}
}
return ans;
}
'Computer Science > 알고리즘' 카테고리의 다른 글
[파이썬 알고리즘 인터뷰] 7. 빗물 트래핑 (0) | 2022.02.05 |
---|---|
[파이썬 알고리즘 인터뷰] 6. 두 수의 합 (0) | 2022.02.02 |
[파이썬 알고리즘 인터뷰] 4. 그룹 애너그램 (0) | 2022.02.02 |
[파이썬 알고리즘 인터뷰] 3. 가장 흔한 단어 (0) | 2022.01.31 |
[파이썬 알고리즘 인터뷰] 2. 문자열 뒤집기 (0) | 2022.01.31 |