LeetCode 회문 문자열 찾기

LeetCode의 5. Longest Palindromic Substring medium단계의 문제입니다.

 

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"

 

해당 문제는 주어진 문자열 s 에서 가장 긴 회문을 찾는것입니다.

회문이란 문자열을 뒤집었을 경우에도 같은것을 의미합니다.  예시) aaa, 우영우

시작index와 끝index로 투포인터로 나눠서, 끝index를 하나씩 늘려가며, 모든 단어에 대해 회문검사를 실시하고, result를 변경해주는 방식으로 풀었습니다.

 

 

var longestPalindrome = function (s) {

  let result = "";

  for (let i = 0; i < s.length; i++) {

    for (let j = 0; j < s.length; j++) {

      const word = s.slice(i, j + 1);

      if (isPalindrome(word) && word.length >= result.length) {

        result = word;

      }

    }

  }

  return result;

};

function isPalindrome(s) {

  for (let i = 0; i < Math.floor(s.length / 2); i++) {

    if (s[i] !== s[s.length - 1 - i]) return false;

  }

  return true;

}

시간초과로 실패한 코드입니다.

이중 for문으로 O(n^2) , 회문검사함수 O(n) 이므로, O(n^3) 의 시간복잡도를 가지게됩니다.

 

 

var longestPalindrome = function (s) {

  if (s.length < 1) return "";

  let start = 0,

    end = 0;

  for (let i = 0; i < s.length; i++) {

    let length1 = expandAroundCenter(s, i, i);

    let length2 = expandAroundCenter(s, i, i + 1);

    let longest = Math.max(length1, length2);

    if (longest > end - start) {

      start = i - Math.floor((longest - 1) / 2);

      end = i + Math.floor(longest / 2);

    }

  }

  return s.substring(start, end + 1);

};

function expandAroundCenter(s, left, right) {

  while (left >= 0 && right < s.length && s[left] === s[right]) {

    left--;

    right++;

  }

  return right - left - 1;

}

해당코드는 left와 right를 가장자리로 확장해나가며, 계속해서 회문인지 검사합니다.

length1과 length2로 나눈이유는 홀수 글자와 짝수 글자 2개를 비교해서 둘중에 더 긴 회문을 찾기위함입니다.

지금구한 회문의 길이가 현재저장된 회문보다 길다면 변경해줍니다.

문자를 중심부터 확장해나가는 방법을 통해 시간복잡도를 O(n^2) 로 만들어줄수 있습니다.