[leetcode] Longest Palindromic Substring (swift)

문제

https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

문제 요약 

앞으로 읽어도 뒤로 읽어도 같은 가장 긴 부분 문자열을 구하는 문제입니다. 

풀이 

문자열의 시작점과 끝점을 구하고 그 사이의 부분 문자열의 Palindromic 여부를 확인하는 방법이 있습니다. 브루트포스로 효율적인 방법은 아닙니다. 문자열의 길이가 N이라고 한다면 시작점과 끝점을 구하기 위해 O(N^2)의 시간복잡도가 필요합니다. 부분 문자열의 Palindromic 여부를 확인하는 시간도 추가되어야 하는데, 문자열이 전체가 Palindromic일 경우(최악) O(N)의 시간복잡도를 생각할 수 있습니다. 

풀이 코드 1

Runtime 3074ms | Memory 14.4 MB

이 풀이 방식의 시간복잡도는 최악입니다. 

 

다른 방법을 생각해봅니다. 위 풀이 방식을 개선해본다면, 부분 문자열의 시작점과 끝점을 구할 필요가 없습니다. 중심점만 알면 됩니다. 

문자열을 순회하며 중심점이라고 생각하고 Palindromic을 확인하는 방식입니다. 그리고 Palindromic을 확인하는 규칙 2가지를 발견할 수 있습니다.

 

1) 문자열을 반으로 접었을 때 대칭입니다. -> 홀수, 짝수의 케이스를 고려해야합니다.

2) 처음과 끝 사이 문자가 1개일 때는 무조건 Palindromic입니다. -> 홀수일 경우 중간문자 1개는 무시해도 됩니다. 

 

따라서 문자열의 길이가 홀수일 때와 짝수일 때 두가지 경우를 모두 고려해봅니다. 

문자열의 길이가 홀수일 때, 문자열은 중심 문자에서 왼쪽과 오른쪽의 i만큼의 문자를 비교하며 같을 때까지의 길이를 구하며 가장 긴 부분 문자열일 경우 업데이트합니다. 문자열의 길이가 짝수일 때, 문자열은 중심 문자가 없기 때문에 i와 i+1의 문자를 중심이라 생각하고 서로 비교하며 가장 긴 부분 문자열일경우 업데이트합니다.

풀이 코드 2

Runtime 33ms | Memory 14.5 MB