Iterative solution using table (Java)


  • 1
    A
    /**
     * create a table of size s.length() + 1, all initialize to null except first one.
     * each cell contains a list of paths that can reach this cell;
     * if a cell is not null (reachable), we try to move to next cell by finding palindromes
     * in the substring.
     * in the end, the last cell should contain results.
     * the table takes care of DP/ memoization.
     */
    

    Code:

    public List<List<String>> partition(String s) {
        List<List<List<String>>> table = new ArrayList<List<List<String>>>(s.length() + 1);
        List<List<String>> lists0 = new ArrayList<List<String>>();
        lists0.add(new ArrayList<String>());
        table.add(lists0);
        for (int i = 1; i <= s.length(); i++)
            table.add(null);
        for (int i = 0; i <= s.length(); i++) {
            List<List<String>> lists = table.get(i);
            if (lists != null) {
                for (int end = i + 1; end <= s.length(); end++) {
                    String next = s.substring(i, end);
                    if (isPalindrome(next)) {
                        List<List<String>> nextLists = table.get(end);
                        if (nextLists == null) {
                        	nextLists = new ArrayList<List<String>>();
                        	table.set(end, nextLists);
                        }
                        for (List<String> list : lists) {
                            List<String> nextList = new ArrayList<String>(list);
                            nextList.add(next);
                            nextLists.add(nextList);
                        }
                    }
                }
            }
        }
        
        return table.get(s.length());
    }
    
    private boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right))
                return false;
            left++;
            right--;
        }
        return true;
    }

Log in to reply
 

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