[Leetcode] 131. Palindrome Partitioning

Problem

문제 링크

쪼개서 나올 수 있는 팰린드롬의 경우의 수를 구하는 문제

Solution

input: 'aaabbc'
output: [
  ['a', 'a', 'a', 'b', 'b', 'c'],
  ['a', 'a', 'a', 'bb', 'c'],
  ['a', 'aa', 'b', 'b', 'c'],
  ['a', 'aa', 'bb', 'c'],
  ['aa', 'a', 'b', 'b', 'c'],
  ['aa', 'a', 'bb', 'c'],
  ['aaa', 'b', 'b', 'c'],
  ['aaa', 'bb', 'c'],
]

위 테스트케이스를 입력하고 돌렸을때, 가장 작은 사이즈의 팰린드롬부터 구해지고, 오른쪽의 값을 작은 단위라고했을때 점점 단위가 커지는 순서로 배치되고 있는것을 알 수있다. 이 패턴을 이용해서 DFS를 구현하면 된다.

작은 단위로 쪼개면서 깊은 뎁스로 진입한다. 모든 요소를 검사했다면 팰린드롬의 값을 저장한다. 이때 순서상 특정 문자열을 검사할때 팰린드롬이 아니라면 깊은 뎁스로 들어가지 못하도록 조건처리를 한다. 최종 뎁스에서 팰린드롬으로 검사된 값(배열)은 이전뎁스에서도 팰린드롬이기 때문에 이전뎁스에서 검사할 문자의 길이를 늘려가면서 검사하도록 한다.

JS Code

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  const isPalindrome = str =>
    Array.from(str)
      .reverse()
      .every((c, i) => c === str[i])

  let answer = []

  function dfs(left = 0, arr = []) {
    if (left === s.length) answer.push([...arr])

    for (let right = left + 1; right <= s.length; right++) {
      const substr = s.substring(left, right)

      if (!isPalindrome(substr)) continue

      arr.push(substr)
      dfs(right, arr)
      arr.pop()
    }
  }
  dfs()
  return answer
}