Longest Padlindromic Substring

Wonseok Lee·2021년 4월 20일

leetcode longest palindromic substring

LeetCode

목록 보기

3/3

이 포스트에서는 leetcode의 Longest Palindromic Substring 문제를 다뤄보도록 하겠다.

문제링크: Longest Palindromic Substring
솔루션: source code

1. 문제분석

주어진 문제를 간단하게 요약해보면 아래와 같다.

임의의 길이를 갖는 string이 주어집니다. string 내의 substring 중에서 가장 길이가 긴 녀석을 출력해주세요. 만약, 그러한 substring이 여러 개라면 그 중 아무거나 출력해도 좋습니다.

2. 가장 멍청한 풀이

섹션의 제목이 '가장 멍청한 풀이' 이기는 하지만 알고리즘을 공부할 때 가장 멍청한 풀이부터 가장 스마트한 풀이까지 사고의 흐름을 정리하는 과정은 매우 중요하다.

따라서, 이 섹션에서 '가장 멍청한 풀이' 에 대해서 꼭 한번 짚고 넘어가고자 한다.

지구인이라면 임의의 string s에 대해서 그 substring s[begin:end]가(Python에서처럼 개폐구간을 의미함)가 palindrome인지 아닌지를 판단하는 함수는 눈을 감고도 만들어 낼 수 있다.

가장 멍청한 풀이는 s에 존재할 수 있는 모든 substring s[begin:end] $(0<=begin<end<=s.length)$ 에 대해서 palindrome인지의 여부를 판단하고, 가장 길이가 긴 녀석을 찾는다.

코드로 옮기면, 아래와 같다.

class Solution
{
public:
  bool isPalindrome(const string& s, int begin, int end)
  {
    while (begin < end)
    {
      if (s[begin++] != s[--end])
      {
        return false;
      }
    }

    return true;
  }

  string longestPalindrome(string s)
  {
    int lps_pos = 0;     // Start position of 'Longest Palindromic Substring'
    int lps_length = 0;  // Length of 'Longest Palindromic Substring'

    for (int begin = 0; begin < s.length(); ++begin)
    {
      for (int end = begin + 1; end <= s.length(); ++end)
      {
        if (isPalindrome(s, begin, end) && lps_length < end - begin)
        {
          lps_pos = begin;
          lps_length = end - begin;
        }
      }
    }

    return s.substr(lps_pos, lps_length);
  }
};

위의 풀이는 속도를 기준으로 5%, 메모리를 기준으로 94% 정도의 백분위를 받을 수 있다.

제시한 풀이는 주어진 string의 길이를 $n$ 이라고 할 때, 각 substring의 palindrome 판단에 $O(n)$ , 존재할 수 있는 substring의 수는 $O(_nC_2)=O(n^2)$ 이므로 총 $O(n^3)$ 의 시간복잡도를 갖는다.

3. 적당히 똑똑한 풀이

이번 섹션에서는 섹션 2에서 $O(n^3)$ 이었던 시간복잡도를 $O(n^2)$ 로 만들어보려한다.

제안할 아이디어의 핵심을 꿰뚫는 질문은 "만약, string에 있는 모든 palindrome의 길이가 홀수라는 보장이 있다면 더 빨리 풀 수 있나요?"이다.

조금 더 부연하여 설명하면, 아래와 같이 문제가 변형되서 주어진다면 더 빨리 풀 수 있는가에 대한 질문이다.

임의의 길이를 갖는 string이 주어집니다. string 내의 substring 중에서 가장 길이가 긴 녀석을 출력해주세요. 만약, 그러한 substring이 여러 개라면 그 중 아무거나 출력해도 좋습니다. string에 존재하는 모든 palindrome은 길이가 홀수임을 만족하도록 입력이 주어집니다. 즉, babab는 주어질 수 있어도 cbbd 같은 string은 주어지지 않습니다.

조금만 머리를 써보면, 더 빨리 풀어낼 수 있는데 아래에 그 아이디어를 설명해보도록 하겠다.

'적당히 똑똑한 풀이'는 str[i](for all $0<=i<s.length$ )를 중심으로하는 가장 긴 palindrome을 찾는다.

아래의 그림을 보면, str[i]를 중심으로 좌우로 문자를 비교해 나가며, str[i]를 중심으로 하는 가장 긴 palindrome을 찾고 있는 것을 볼 수 있다.

별다를 것은 없지만, 후술의 편의를 위해 몇 가지 용어를 정의하고 넘어가고자 한다.

expand: str[i]를 중심으로 좌우로 문자를 비교해나가는 행위를 "str[i]를 expand한다"고 부르도록 하자.
radius: str[i]를 중심으로 하는 가장 긴 palindrome의 반지름으로 정의하자. 모든 palindrome의 길이가 홀수라는 가정 위에서 문제를 풀고 있으므로 어렵지 않게 정의할 수 있다.

이 방법은 주어진 문자열의 길이를 $n$ 이라고 할 때, 각 str[i]의 expand에 $O(n)$ , str[i]를 고르는 데 $O(n)$ 이므로 총 $O(n^2)$ 의 시간복잡도를 갖는다.

아니 잠깐!, 근데 우리가 풀어야 될 문제에 모든 palindrome의 길이가 홀수라는 제약 조건 자체가 없지 않은가?

이는 사전에 주어진 string에 약간의 전처리를 해줌으로써 쉽게 달성할 수 있다.

이 전처리는 주어지는 string의 각 문자 사이사이에 임의의 특수문자를 끼워 넣어주는 것인데, 이를 수행하면 string 내에 존재하는 모든 palindrome의 길이가 홀수가 되게된다.

보다 구체적으로 이야기하면, babab와 같이 입력이 주어질 때 이를 $b$a$b$a$b$와 같이 전처리한 뒤 상술한 아이디어(str[i]를 expand하는)를 적용하라는 것이다.

왜 전처리를 수행하면 string 내에 존재하는 모든 palindrome의 길이가 홀수가 되게되는지는 아래의 정성적인 증명을 통해 이해해보도록 하자.

임의의 palindrome $s$ 에 대해, $s$ 의 각 문자 사이사이에 동일한 문자 $\$$ 를 끼워 넣은 $s_\$$ 역시 여전히 palindrome이다.
임의의 palindrome $s$ 의 길이가 짝수였다면, $s$ 의 각 문자 사이사이에 동일한 문자 $\$$ 를 끼워 넣은 $s_\$$ 의 길이는 홀수가 된다(홀수개의 $\$$ 가 삽입되므로).
임의의 palindrome $s$ 의 길이가 홀수였다면, $s$ 의 각 문자 사이사이에 동일한 문자 $\$$ 를 끼워 넣은 $s_\$$ 의 길이는 여전히 홀수가 된다(짝수개의 $\$$ 가 삽입되므로).

결론적으로 위의 전처리 과정을 수행한 뒤, str[i]를 expand하는 알고리즘을 수행하여 얻어진 longest palindromic substring에서 전처리 때 삽입된 문자를 제외하고 출력해주면 원래 문제의 답을 얻을 수 있다.

이를 코드로 정리하면 아래와 같다.

class Solution
{
public:
  string getPreprocessed(const string& s)
  {
    string preprocessed;

    for (int i = 0; i < s.size(); ++i)
    {
      preprocessed.push_back('$');
      preprocessed.push_back(s[i]);
    }
    preprocessed.push_back('$');

    return preprocessed;
  }

  int getRadius(const string& s, int i)
  {
    int radius = 0;
    int l = i - 1;
    int r = i + 1;
    while (0 <= l && r < s.length())
    {
      if (s[l--] == s[r++])
      {
        ++radius;
      }
      else
      {
        break;
      }
    }

    return radius;
  }

  string filter(const string& preprocessed, int lps_pos, int lps_radius)
  {
    string filtered;

    for (int i = 0; i < 2 * lps_radius + 1; ++i)
    {
      if (preprocessed[lps_pos - lps_radius + i] != '$')
      {
        filtered.push_back(preprocessed[lps_pos - lps_radius + i]);
      }
    }

    return filtered;
  }

  string longestPalindrome(string s)
  {
    int lps_pos = 0;     // Start position of 'Longest Palindromic Substring'
    int lps_radius = 0;  // Radius of 'Longest Palindromic Substring'

    string preprocessed = getPreprocessed(s);

    for (int i = 0; i < preprocessed.length(); ++i)
    {
      int radius = getRadius(preprocessed, i);
      if (radius > lps_radius)
      {
        lps_pos = i;
        lps_radius = radius;
      }
    }

    return filter(preprocessed, lps_pos, lps_radius);
  }
};

위의 풀이는 속도를 기준으로 70%, 메모리를 기준으로 70% 정도의 백분위를 받을 수 있다.

4. 조금 더 똑똑한 풀이

사실 이 문제는 "Manacher's Algorithm"이라 불리는 $O(n)$ 짜리 해답이 존재하는 문제이다.

필자의 경우는 "Manacher's Algorithm"을 문제를 다 풀고 나서야 읽어보게 되었는데, 생각보다 간단하고 눈여겨봐둘만한 부분이 있는 것 같아 별도로 정리하고자 한다.

전체적인 풀이의 틀은 섹션 3과 동일한데(전처리 및 후처리), 단지 이전에 구해놓은 lps_radius들을 활용해서 expand할 필요가 없는 곳들은 과감히 skip한다는 점이 다르다.

"Manacher's Algorithm"은 str[i]를 expand할 때 for all $j(0<=j<i)$ 에 대해 아래의 것들이 이미 구해져 있다는 것을 가정한다.

radius[j]: str[i]를 중심으로 하는 palindrome의 반지름
rightmost_center: j+radius[j]가 최대가 되게하는 j

radius[j]는 의미가 명확한데, rightmost_center의 경우 "뭐래?"라고 생각하는 독자들이 꽤 있으리라 생각된다.

사실 말로 풀어쓰니 어렵지 그려보면 정말 별거 아닌데, rightmost_center 아래 그림이 보이는 것과 같이 자신을 중심으로 하는 palindrome이 가장 오른쪽까지 미치는 녀석의 인덱스를 의미한다.

아래 그림에서는 rightmost_center는 i-3이 될텐데, 실제로 str[i-3]에서 expand된 palindrome이 가장 오른쪽까지 미쳐있는 것을 알 수 있다.(그림에서는 i+1까지)

"Manacher's Algorithm"은 str[i]를 expand할 때, i와 rightmost_center 사이의 관계에 따라 아래와 같이 동작한다.

Case 1) rightmost_center >= i인 경우
- 그림으로 표현하면 아래와 같은 경우일 것이다.
- 잘 생각해보면 str[i]를 처음부터 무식하게 expand를 해줄 필요가 없는데, 아래 불렛에서 차근차근 알아보자.
- str[i]가 str[rightmost_center]를 중심으로 하는 palindrome에 속해있으므로 반드시 str[i]의 거울상에 대응되는 str[mirror]가 아래 그림과 같이 존재할 것이다.
- 상술했던 가정에 따라 radius[mirror]는 이미 구해져 있을 것이고, 적어도 str[mirror]를 중심으로 하는 palindrome 중에서 str[rightmost_center]를 중심으로 하는 palindrome에 속하는 문자들만큼은 아래 그림과 같이 str[i]를 중심으로도 동일하게 나타날 것이다.
- 따라서, str[i]는 expand를 시작할 때, radius[mirror]만큼 떨어진 문자부터 시작할 수 있다.
Case 2) rightmost_center < i인 경우
- 별다른 힌트를 얻을 수 없는 경우이다.
- 그냥 처음부터 expand해준다.

상술한 내용을 그대로 코드로 옮기면 아래와 같다.

class Solution
{
public:
  string getPreprocessed(const string& s)
  {
    string preprocessed;

    for (int i = 0; i < s.size(); ++i)
    {
      preprocessed.push_back('$');
      preprocessed.push_back(s[i]);
    }
    preprocessed.push_back('$');

    return preprocessed;
  }

  int getRadius(const string& s, int i, int hint)
  {
    int radius = hint;
    int l = i - hint - 1;
    int r = i + hint + 1;
    while (0 <= l && r < s.length())
    {
      if (s[l--] == s[r++])
      {
        ++radius;
      }
      else
      {
        break;
      }
    }

    return radius;
  }

  string filter(const string& preprocessed, int lps_pos, int lps_radius)
  {
    string filtered;

    for (int i = 0; i < 2 * lps_radius + 1; ++i)
    {
      if (preprocessed[lps_pos - lps_radius + i] != '$')
      {
        filtered.push_back(preprocessed[lps_pos - lps_radius + i]);
      }
    }

    return filtered;
  }

  string longestPalindrome(string s)
  {
    int lps_pos = 0;     // Start position of 'Longest Palindromic Substring'
    int lps_radius = 0;  // Radius of 'Longest Palindromic Substring'

    string preprocessed = getPreprocessed(s);

    int rightmost_center = 0;
    vector<int> radius(preprocessed.length(), 0);

    // Obviously, radius[0] is 0. So we can  start iteration from i = 1
    for (int i = 1; i < preprocessed.length(); ++i)
    {
      int hint;

      // Case 1
      if (rightmost_center + radius[rightmost_center] >= i)
      {
        int mirror = rightmost_center - (i - rightmost_center);
        hint = min(radius[mirror], mirror - (rightmost_center - radius[rightmost_center]));
      }
      // Case 2
      else
      {
        hint = 0;
      }

      radius[i] = getRadius(preprocessed, i, hint);

      if (radius[i] > lps_radius)
      {
        lps_pos = i;
        lps_radius = radius[i];
      }

      if (i + radius[i] > rightmost_center + radius[rightmost_center])
      {
        rightmost_center = i;
      }
    }

    return filter(preprocessed, lps_pos, lps_radius);
  }
};

위에 보인 구현은 시간복잡도 기준 96%, 공간복잡도 기준 61% 정도의 백분위를 받을 수 있다.

Wonseok Lee

Pseudo-worker

이전 포스트