LeetCode No.5 - Longest Palindromic Substring

카테고리: Algorithms

January 14, 2022

문제링크

접근

문자열을 한 번 순회하는 포인터를 기준으로 짝수 길이의 팰린드롬과 홀수 길이의 팰린드롬을 탐색하는 슬라이딩 윈도우 두 개를 돌리는 방식으로 접근했습니다.

approach
포인터 i와 두 개의 슬라이딩 윈도우

자바스크립트 구현

function findPalindrome(s, l, r) {
  const { length } = s;
  while (l >= 0 && r < length && s[l] === s[r]) {
    l--;
    r++;
  }
  return s.substring(l + 1, r);
}
  
const findOddLengthPalindrome = (s, idx) => findPalindrome(s, idx - 1, idx + 1);
const findEvenLengthPalindrome = (s, idx) => findPalindrome(s, idx, idx + 1);

function longestPalindrome(s) {
  const { length } = s;
  let answer = '';

  for (let i = 0; i < length; i++) {
    const oddLengthCandidate = findOddLengthPalindrome(s, i);
    const evenLengthCandidate = findEvenLengthPalindrome(s, i);

    if (answer.length < oddLengthCandidate.length) answer = oddLengthCandidate;
    if (answer.length < evenLengthCandidate.length) answer = evenLengthCandidate;
  }
  return answer;
}