LeetCode #5 Longest Palindromic Substring

문제

문자열 s가 주어지면 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.

제출코드

/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = (s) => {
  let answer = s[0];
  for (let i=0; i < s.length; i++) {
    for (let j=i+answer.length; j < s.length; j++) {
      if (s[i] === s[j] && isPalindrome(s, i, j) ) {
        answer = s.slice(i, j+1);
      } 
    }
  }
  return answer;
};

const isPalindrome = (string, left, right) => {
  let returnIsPalindrome = true;
  while (left < right) {
    if (string[left] !== string[right]) {
      return returnIsPalindrome = false;
    }
    left++;
    right--;
  }
  return returnIsPalindrome;
}

풀이

주어진 문자열에서 가장 긴 회문을 찾는 문제이다.

우선 answer에 주어진 문자열의 가장 첫번제 문자를 대입한다. 그렇게 되면 answer은 현재 찾은 가장 긴 회문이다.

이를 이용해서 2중for문을 사용한다. 주어진 문자열과 i(왼쪽인덱스)와 j(오른쪽인덱스)를 회문을 구하는 함수에 매개변수로 준다.

isPalindrome에서 주어진 인덱스 위치의 문자들이 같은지를 확인하고 왼쪽인덱스는 ++, 오른쪽은--를 하여 대칭이 맞는지를 확인해준다.