131. Palindrome Partitioning

문제링크:https://leetcode.com/problems/palindrome-partitioning/

Palindrome의 배열로 해당 문자열을 나누는 경우의 수를 모두 출력하는 문제다.

Solution

Recursion

앞에서 일정 구간의 palindrome을 구하면 나머지 문자열은 다시 같은 문제가된다. 재귀를 구현하기 위해 문자열을 palindrome의 묶음으로 나타내는 함수를 getPartition이라고 하자. 이후 앞에서 일정 부분의 palindrome을 얻었다면 나머지 부분은 다시 getPartition을 통해 더 작지만 같은 형태의 문제로 결과를 얻을 수 있다.

Algorithm

• isPalindrome은 s의 앞과 끝 인덱스를 바탕으로 양쪽을 계속해서 비교해 palindrome인지 알아내는 함수다.
• getPartition에 partition을 얻을 s의 시작과 끝 인덱스를 입력받는다.
• 만약 start > end 인 경우 partition이 없으므로 빈 결과 [[]]를 반환한다.
• start부터 end까지 i로 반복하여 start~i까지의 문자열이 isPalindrome인지 알아낸다.
• isPalindrome인 경우 나머지 부분 i+1~end까지를 다시 getPartition을 통해 partitionResult 얻는다.
• start~i까지의 palindrome문자열을 curResult, i+1~end까지의 partitionResult를 합친다. (partitionResult의 결과를 각각 curResult와 합쳐 result에 push)
• 모든 합쳐진 결과 result를 반환한다.

vvar partition = function(s) {
  // Palindrome 확인 with s's indexes
  const isPalindrome = (start, end) => {
    while (start <= end) {
      if (s[start] !== s[end]) return false;
      start++;
      end--;
    }
    return true;
  }
  
  // Palindrome 으로 나누기 recursion
  const getPartition = (start, end) => { // return [['a','b','a'], ['aba']]
    if (start > end) return [[]];
    const result = [];
    for (let i = start; i <= end; i++) {
      if (isPalindrome(start,i)) {
        const partitionResult = getPartition(i + 1, end);
        const curResult = s.slice(start, i + 1);
        for (let partition of partitionResult) {
          result.push([curResult,...partition]);
        }
      }
    }
    return result;
  }
  
  return getPartition(0, s.length - 1);
};