0131. Palindrome Partitioning

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

Description

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"]]

Constraints:

• 1 <= s.length <= 16

• s contains only lowercase English letters.

ac1: Backtracking, DFS

key:

• isPalindrome();

• think it as array subset problem

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<List<String>>();
        List<String> tmpres = new ArrayList<String>();
        backtrack(s, 0, tmpres, res);
        return res;
    }
    private void backtrack(String s,
                           int start,
                           List<String> tmpres,
                           List<List<String>> res
                          ) {
        if (start > s.length()) return;
        if (start == s.length()) {
            res.add(new ArrayList<String>(tmpres));
            return;
        }

        for (int i = start+1; i <= s.length(); i++) {
            if (!isPalindrome(s.substring(start, i))) continue;
            tmpres.add(s.substring(start, i));
            backtrack(s, i, tmpres, res);
            tmpres.remove(tmpres.size()-1);
        }
    }
    private boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < s.length() && j >= 0; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }
}

ac2: improve isPalindrome

https://leetcode.com/problems/palindrome-partitioning/discuss/41982/Java-DP-%2B-DFS-solution

class Solution {
    boolean[][] isPalindrome;

    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        // Edge cases
        if (s == null || s.length() == 0) {
            return res;
        }

        init(s);

        process(0, s, new ArrayList<>(), res);

        return res;
    }

    private void process(int start, String s, List<String> note, List<List<String>> res) {
        // Exit
        if (start >= s.length()) {
            res.add(new ArrayList<>(note));
            return;
        }

        for (int i = start; i < s.length(); i++) {
            if (isPalindrome[start][i]) {
                note.add(s.substring(start, i+1));
                process(i+1, s, note, res);
                note.remove(note.size() - 1);
            }
        }
    }

    private void init(String s) {
        isPalindrome = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j) && (i - j <= 2 || isPalindrome[j+1][i-1])) {
                    isPalindrome[j][i] = true;
                }
            }
        }
    }
}

ac3: faster

• substring() is O(n) where n is the length of substring.

• class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<List<String>>();
        List<String> tmpres = new ArrayList<String>();
        backtrack(s, 0, tmpres, res);
        return res;
    }
    private void backtrack(String s,
                           int start,
                           List<String> tmpres,
                           List<List<String>> res
                          ) {
        int len = s.length();
        if (start >= len) {
            res.add(new ArrayList<String>(tmpres));
            return;
        }
  
        for (int i = start; i < len; i++) {
            if (isPalindrome(s, start, i)){
                tmpres.add(s.substring(start, i+1));
                backtrack(s, i+1, tmpres, res);
                tmpres.remove(tmpres.size()-1);
            }
  
        }
    }
    private boolean isPalindrome(String s, int l, int r) {
        if (l == r) return true;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
  }

ac4: Memorization + DFS

it's slower and even error-prone

class Solution {
    public List<List<String>> partition(String s) {
        Map<Integer, List<List<String>>> map = new HashMap<Integer, List<List<String>>>();
        return dfs(s, 0, map);
    }
    private List<List<String>> dfs(String s, int start, Map<Integer, List<List<String>>> map) {
        List<List<String>> res = new ArrayList<List<String>>();
        int len = s.length();
        if (start == len) {
            res.add(new ArrayList<>());
            return res;
        } 

        // memorization
        if (map.containsKey(start)) return map.get(start);

        // iterate
        for (int i = start + 1; i <= len; i++) {
            if (isPalindrome(s.substring(start, i))) {
                List<List<String>> child = dfs(s, i, map);
                for (List<String> list : child) {
                    List<String> tmp = new ArrayList<String>();
                    tmp.add(s.substring(start, i));
                    tmp.addAll(list);
                    res.add(tmp);
                }
                // res.addAll(child);
            }
        }

        map.put(start, res);
        return res;
    }
    private boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}
/*
backtracking
memorization + DFS: 1) not visited, 2) visited + result, 3) visited no result
*/