[알고리즘/LeetCode] Longest Palindromic Substring

앞뒤가 똑같은 🎶 전화번호 🎵

주어진 문자를 잘랐을때 앞 뒤의 문자가 똑같으면서 가장 긴 문자를 반환하는 문제입니다. 좌우가 똑같은 문자열이라고 보면 되겠습니다.

abab 가 주어졌을때는 좌측 a 우측 a 중간값 b 로해서 aba 가 가장 긴 문자열이 됩니다. 물론 bab 도 동일합니다.

babab 가 주어진다면 3번째 요소값인 b 를 중심으로 좌우가 똑같게 됩니다. 3번째 요소값을 좌 우로 a 가 배치되고 한층 더 밖으로 나가면 b 가 동일하게 배치되어 있죠?! 이런식으로 좌우가 동일한 문자로 형성된 문자열중에서 가장 긴 문자열을 반환하는 문제입니다.

 

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

Longest Palindromic Substring - LeetCode

 

 

일단 가장 처음으로 진행했던 방식은 조금은 무식하지만 for 문으로 문자를 앞부터 뒤까지 돌고 그 안에는 while 문으로 잘린 문자열이 홀수냐 짝수냐의 방식에 맞춰서 앞과뒤가 같은지 확인하도록 만들었습니다.

class Solution {
  String longestPalindrome(String s) {
    int len = s.length;

    if (len < 2) {
      return s;
    }

    String temp = '';
    String max = '';

    for (int i = 0; i < len; i++) {
      int start = i;
      int end = i + 1;
      while (start >= 0 && end <= len - 1) {
        if (s[start] != s[end]) {
          break;
        } else {
          temp = s.substring(start, end + 1);
          start--;
          end++;
        }
      }

      if (max.length < temp.length) {
        max = temp;
      }
    }

    for (int i = 0; i < len; i++) {
      int start = i;
      int end = i + 2;
      while (start >= 0 && end <= len - 1) {
        if (s[start] != s[end]) {
          break;
        } else {
          temp = s.substring(start, end + 1);
          start--;
          end++;
        }
      }

      if (max.length < temp.length) {
        max = temp;
      }
    }

    if (max.isEmpty) {
        max = s[0];
      }
    return max;
  }
}

 

 

 

더 나은 방법 Better Way

중심값에서 퍼져나가면서 비교한다는 개념은 비슷합니다. 동일한 비교 코드를 홀수냐 짝수냐에 따라서 비교하는 값의 시작 값을 다르게 표시했습니다.

추가로 신경써야할 부분은 주어진 문자가 1개 혹은 2개일때도 앞뒤가 똑같은 문자를 반환해야 합니다. 1개일 경우에는 그냥 자신을 뱉어내면 되고 만약 2개일 경우에 비교해서 2개를 반환하던 혹은 1개를 반환하던 해야합니다.

 

중심은 중간값에서부터 좌우 혹은 앞뒤로 멀어지면서 비교를 해야한다는 것입니다.

 

class Solution {
  String longestPalindrome(String s) {
    int n = s.length;
    if (n <= 1) return s;

    int bestL = 0, bestR = 0;

    List<int> expand(int l, int r) {
      while (l >= 0 && r < n && s[l] == s[r]) {
        l--;
        r++;
      }
      return [l + 1, r - 1];
    }

    for (int i = 0; i < n; i++) {
      var odd = expand(i, i);
      if (odd[1] - odd[0] > bestR - bestL) {
        bestL = odd[0];
        bestR = odd[1];
      }

      var even = expand(i, i + 1);
      if (even[1] - even[0] > bestR - bestL) {
        bestL = even[0];
        bestR = even[1];
      }
    }

    return s.substring(bestL, bestR + 1);
  }
}