[131] Palindrome Partitioning

[tsungtingdu]

var partition = function(s) {

    const ans = []
    function traverse(str, arr) {
    if (str.length === 0 && arr.length !== 0) { 
          ans.push(arr)
          return
        }
    }

    for (let i = 0; i < str.length; i++) {
        const subs = str.substring(0, i + 1)
        if (check(subs)) {
           traverse(str.substring(i+1), [...arr, subs])
        }
    }
    traverse(s, [])
    return ans
}

function check (str) {
    if (str.length === 0) return false

    let left = 0
    let right = str.length - 1

    while(left < right) {
        if (str[left] !== str[right]) {
            return false
        }
        left++
        right--
    }
    return true
}

[henry22]

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    const res = [];
    dfs(s, []);
    return res;

    function dfs(s, temp) {
        if(!s.length) {
            res.push(temp.slice());
        }

        for(let i = 1; i < s.length + 1; i++) {
            if(isPalindrome(s.slice(0, i))) {
                temp.push(s.slice(0, i));
                dfs(s.slice(i), temp);
                temp.pop();
            }
        }
    }

    function isPalindrome(s) {
        return s === s.split('').reverse().join('');
    }
};