解題程式碼

const isPalindrome = (s) => s === s.split('').reverse().join('');

var partition = function (s) {
  const result = [];

  const backTracking = (path, index) => {
    if (index === s.length) result.push([...path]);

    for (let i = index + 1; i <= s.length; i++) {
      let subStr = s.slice(index, i);

      if (isPalindrome(subStr)) {
        path.push(subStr);
        backTracking(path, i);
        path.pop();
      }
    }
  };
  backTracking([], 0);

  return result;
};

解題思路、演算法

這題用回溯法解題，要想到遞迴的中止條件有兩個:

1. 已經走到 input 字串 s 的最後索引，蒐集回文字串的陣列 path 會被加入結果
2. 若回溯過程找到的子字串不是回文，就不繼續遞迴下去

概念圖:

解法的時間、空間複雜度

時間複雜度: O(2^n * n)，n 的部分精確來說是 3 * n，判斷字串是否是回文
空間複雜度: O(n)

參考資料

Palindrome Partitioning - Backtracking - Leetcode 131

「代码随想录」带你学透回溯算法！131. 分割回文串