[LeetCode] 214. Shortest Palindrome

😎풀이

1. 접두 & 접미사 체크
2. 모두 접두사이자 접미사라면 그대로 반환
3. 펠린드롬이 아닌 부분 확인
4. 조합 후 반환

function shortestPalindrome(s: string): string {
  const length = s.length;
  if (!length) return s;
  let left = 0;
  // 접두 & 접미사 체크
  for (let right = length - 1; right >= 0; right--) {
    if (s.charAt(right) === s.charAt(left)) {
      left++;
    }
  }
  // 모두 접두사이자 접미사라면 그대로 반환
  if (left === length) {
    return s;
  }
  // 펠린드롬이 아닌 부분
  const nonPalindromeSuffix = s.substring(left);
  // 역순
  const reverseSuffix = nonPalindromeSuffix.split('').reverse().join('');
  // 역순 + 펠린드롬 재귀 확인 + 펠린드롬이 아닌 부분 결합하여 반환
  return reverseSuffix + shortestPalindrome(s.substring(0, left)) + nonPalindromeSuffix;
};