[Leetcode] 5. Longest Palindromic Substring

Problem

문제 링크

최고로 긴 팰린드롬을 구하는 문제

Solution

1. palindromic 함수를 만든다.
2. 문자열을 처음부터 시작한다.
3. 마지막 문자 값을 비교하며 팰린드롬인지 확인한다.
4. 맞다면 그 길이를 저장하고 아니라면 3번과정을 반복한다.
5. 마지막 문자에서 처음 시작문자까지 도착하면 처음에서 다음 문자로 이동하고 3~4번 과정을 반복한다.

• 팰린드롬인지 파악하기전에 이전에 팰린드롬인적이 있다면 길이를 가지고있다가 비교할 문자열 길이를 비교하여 조건처리를한다.
  속도를 올릴 수 있다.

JS Code

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let maxLenStr = ''

  for (let i = 0; i < s.length; i++) {
    if (maxLenStr.length > s.length - i) break

    let j = s.lastIndexOf(s[i])
    let temp = s.substring(i, j + 1)

    while (i < j) {
      if (maxLenStr.length < temp.length && isPalindromic(temp)) {
        maxLenStr = temp
        break
      }
      j = s.lastIndexOf(s[i], j - 1)
      temp = s.substring(i, j + 1)
    }
  }

  return maxLenStr || s[0]
}

const isPalindromic = str => {
  let [start, end] = [0, str.length - 1]

  while (start < end) {
    if (str[start++] !== str[end--]) return false
  }

  return true
}