[LeetCode] 5. Longest Palindromic Substring

Problem

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Solution

Approach

1. 문자열 내에서 각 문자를 참조한다.

2. 해당 문자를 기준으로 좌측과 우측의 문자를 확인하여 Palindrome에 해당하는지 확인하고 가장 긴 문자열을 메모한다.

3. 메모된 문자열을 반환한다.

Algorithm

Complexity Analysis

• Time Complexity

최악(Worst) : 문자열이 모두 같은 문자로 이루어져 있다면 for반복문(4)를 통해 어느 문자를 참조하더라도 Palindrome이 되고 for반복문(4) 내의 while반복문들이 문자열 s의 길이(n)만큼 매번 실행되므로 총 n + n + … + n = n * n = n^2의 실행횟수를 가진다. 따라서 O(n^2)의 시간 복잡도를 가진다.

평균(Average) : for반복문(4)을 통해 문자열을 참조할 때, for반복문(4)내의 while반복문들이 문자열의 절반씩만 참조하는 경우에 총 n / 2 + n / 2 + … + n / 2 = n^2 / 2번의 실행횟수를 가진다. 따라서 O(n^2)의 시간 복잡도를 가진다.

최선(Best) : 문자열 내에서 Palindrome이 존재하지 않아 for반복문(4) 내의 while반복문들이 한 번씩만 수행되는 최선의 경우에는 for반복문(4)이 문자열 s의 길이(n)만큼 실행되므로 O(n)의 시간 복잡도를 가진다.

• Space Complexity

문자열 s의 길이(n)에 따라 증가하거나 감소되어 할당받는 메모리 공간이 없으므로 모든 경우에 O(1)의 공간 복잡도를 가진다.