Java Backtracking solution beats 100%


  • 0
    H

    First, build a 2d n*n String array isPalindrome in O(n^2) time, where isPalindrome[i][j] means that s.substring(i, j + 1) is a palindrome.
    Then, backtrack starting from index 0 to compute all possible lists of palindromes, adding them to the result when the recursing index reaches the end of the string.

    public class Solution {
        public List<List<String>> partition(String s) {
            List<List<String>> res = new ArrayList<>();
            if(s == null || s.length() == 0)
                return res;
            int n = s.length();
            String[][] isPalindrome = new String[n][n];
            buildSubPalindromes(s, isPalindrome);
            backtrack(res, new ArrayList<>(), isPalindrome, 0);
            return res;
        }
        
        public void backtrack(List<List<String>> res, List<String> curr, String[][] isPalindrome, int idx) {
            if(idx == isPalindrome.length) {
                res.add(new ArrayList<>(curr));
                return;
            }
            
            for(int i = idx; i < isPalindrome.length; ++i) {
                if(isPalindrome[idx][i] != null) {
                    curr.add(isPalindrome[idx][i]);
                    backtrack(res, curr, isPalindrome, i + 1);
                    curr.remove(curr.size() - 1);
                }
            }
        }
        
        public void buildSubPalindromes(String s, String[][] isPalindrome) {
            int n = s.length();
            for(int i = 0; i < n; ++i) {
                int left = i;
                int right = i;
                while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                    isPalindrome[left][right] = s.substring(left, right + 1);
                    --left;
                    ++right;
                }
                
                left = i - 1;
                right = i;
                while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                    isPalindrome[left][right] = s.substring(left, right + 1);
                    --left;
                    ++right;
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.