131. Palindrome Partitioning (Medium)

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

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

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

Solutions

class Solution {

    // key is the substring, value is whether it is palindrome or not.
    Map<String, Boolean> validPalindromes = new HashMap<>();

    // strings or substrings of them can not form the palindrome
    Map<String, Boolean> unpartitionableStrs = new HashMap<>();

    Map<String, List<List<String>>> solutions = new HashMap<>();

    public List<List<String>> partition(String s) {
        if (s == null || s.isEmpty()) {
            return null;
        }

        // Sort out all the possible substrings that satisfy all criterion of palindrome string.
        sortOutPalindrome(s);

        recurse(s);

        return solutions.get(s);
    }

    private void sortOutPalindrome(String s) {
        // i is the length of palindrome
        for (int i = 1; i <= s.length(); i++) {

            // j is the start index of the palindrome
            for (int j = 0; j < s.length() - i + 1; j++) {
                String str = s.substring(j, j + i);

                // every single char is a valid palindrome
                if (i == 1) {
                    validPalindromes.put(str, true);
                    continue;
                }

                // find out all the palindrome of length 2
                if (i == 2) {
                    if (str.charAt(0) == str.charAt(1)) {
                        validPalindromes.put(str, true);
                    } else {
                        validPalindromes.put(str, false);
                    }

                    continue;
                }

                // for length >= 3
                if (!validPalindromes.get(str.substring(1, i - 1))) {
                    validPalindromes.put(str, false);
                    continue;
                }

                // check out if both side is equal
                if (s.charAt(j) == s.charAt(j + i - 1)) {
                    validPalindromes.put(str, true);
                }
                // not equal and unable to form the palindrome
                else {
                    validPalindromes.put(str, false);
                }
            }
        }
    }

    private List<List<String>> recurse(String substr) {
        List<List<String>> results = new ArrayList<>();

        // partitionable, return solution of length 0.
        if (substr == null || substr.isEmpty()) {
            return results;
        }

        // unpartitionable, return null.
        if (unpartitionableStrs.containsKey(substr)) {
            return null;
        }

        // if already permeated, return the answer
        if (solutions.containsKey(substr)) {
            return solutions.get(substr);
        }

        for (int i = 0; i < substr.length(); i++) {
            String str = substr.substring(0, i + 1);

            // not a valid palindrome, no necessity to dig deep
            if (!validPalindromes.get(str)) {
                continue;
            }

            // tmp is the container to hold possible palindrome arrangements for substr[i+1:].
            List<List<String>> tmp = recurse(substr.substring(i + 1));

            // unpartitionable
            if (tmp == null) {
                continue;
            }

            // Problem occurs if we modify it directly owing to the fact that tmp is possessed substr[i+1:].
            // As a consequence, we are expected to instantiate a brand new List to union str and the results in tmp.
            tmp = union(tmp, str);

            results.addAll(tmp);
        }

        // no possible partition scheme for string s
        if (results.isEmpty()) {
            unpartitionableStrs.put(substr, false);

            return null;
        }

        solutions.put(substr, results);

        return results;
    }

    private List<List<String>> union(List<List<String>> results, String str) {
        List<List<String>> ans = new ArrayList<>();

        // results is empty which means it just hit the end of string.
        if (results.isEmpty()) {
            List<String> tmp = new ArrayList<>();

            tmp.add(str);

            ans.add(tmp);

            return ans;
        }

        for (List<String> sol : results) {
            // create new container to keep values
            List<String> tmp = new ArrayList<>(sol);

            tmp.add(0, str);

            ans.add(tmp);
        }

        return ans;
    }
}

Incorrect Solutions

References