131. Palindrome Partitioning

Leetcode

https://leetcode.com/problems/valid-palindrome/

題目

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

解答

• 方法一

利用 DFS 去 backtracking 所有的迴文子字串

var partition = function(s) {
    // 判斷是否迴文
    const isPalindrome = (start, end) => {
        while(start<end) {
            if(s[start++] !== s[end--]) return false;
        }
        return true;
    }
    
    // 回傳結果
    const res = [];
    // 暫存所有為迴文的子字串
    const temp = [];
    
    const dfs = (start) => {
        // 遍歷過一輪後可以把所有迴文子字串加入到結果矩陣
        if(start>=s.length) {
            // 因為後面有 temp.pop()，會將 res 裡的 temp 也清空，所以這裡要複製一份 temp
            res.push([...temp]);
        }
        let end = start;
        // console.log(start, temp)

        while(end < s.length) {
            if(isPalindrome(start, end)) {
                temp.push(s.substring(start, end+1));
                // 在剩餘字串中繼續尋找迴文子字串
                dfs(end+1)
                // 回到上一輪的 temp 矩陣，end++，繼續尋找迴文子字串
                temp.pop();
            }
            end++;
        }
    }
    dfs(0);
    return res;
};

Runtime: 244 ms, faster than 87.80% of JavaScript online submissions for Palindrome Partitioning.

Memory Usage: 62.2 MB, less than 74.63% of JavaScript online submissions for Palindrome Partitioning.

For example:

s = "aabb"

第一輪從前往後遍歷結束-> temp = ['a', 'a', 'b', 'b']，res = [['a', 'a', 'b', 'b']]

回到上一輪的 temp 矩陣 (temp.pop() 後) -> temp = ['a', 'a', 'b']，start = 3，end = 4

回到上上一輪的 temp 矩陣 (temp.pop() 後) -> temp = ['a', 'a']，start = 2，end = 3

判斷 'bb' 為迴文子字串，將 'bb' 加入 temp -> temp = ['a', 'a', 'bb']，start = 2，end = 3

end+1，繼續 dfs 尋找下一個迴文子字串，如此不斷反覆 backtracking 所有迴文子字串...

• 方法二

利用 dp 的方式求解，dp[len] 代表從 0 ~ len 可組成的迴文子字串矩陣

var partition = function(s) {
    const isPalindrome = (str) => {
      let start = 0;
      let end = str.length-1;
      while(start<end) {
          if(str[start++] !== str[end--]) return false;
      }
      return true;
    }

    const n = s.length;
    const dp = Array.from(Array(n+1), () => []);
    for(let len=1; len<=n; len++) {
        for(let i=0; i<len; i++) {
            const right = s.substring(i, len);
            if(isPalindrome(right)) {
                // 如果從頭到尾整個字串都是迴文，直接 push 進 dp
                if(i === 0) dp[len].push([right]);
                // 從之前的迴文子字串中尋找，如果 right 是迴文的話
                // 只要把之前迴文子字串的值再加上 right 就是新的迴文子字串了
                for(let arr of dp[i]) {
                    const copyArr = [...arr];
                    copyArr.push(right);
                    dp[len].push(copyArr);
                }
            }
        }
    }
    return dp[n];
};

Runtime: 308 ms, faster than 43.76% of JavaScript online submissions for Palindrome Partitioning.

Memory Usage: 71.1 MB, less than 39.12% of JavaScript online submissions for Palindrome Partitioning.

For example:

s = "babab"

dp[0] = []

dp[1] = [ [b] ]

dp[2] = [ [b, a] ]

dp[3] = [ [b, a, b], [bab] ]

dp[4] = [ [b, a, b, a], [bab, a], [b, aba] ]

dp[5] = [ [b, a, b, a, b], [bab, a, b], [b, aba, b], [b, a, bab], [babab] ]

拿 dp[4] 來觀察，前兩個是由 dp[3] + 判斷最後一個 a 是迴文計算而來，第三個是根據 dp[1] + 判斷 aba 迴文而來

測資

let s = "aab";
// s = "aabb";
// s = "babab";

console.log(partition(s))

參考資料

https://hackmd.io/@Ji0m0/B1dUOaRjN/https%3A%2F%2Fhackmd.io%2F%40Ji0m0%2FS1udpfIo_

https://zxi.mytechroad.com/blog/searching/leetcode-131-palindrome-partitioning/