Simple DP + BackTrack - 4ms - Java Sol.


  • 2
    O
    public class Solution {
        public List<List<String>> partition(String s) {
            char[] c = s.toCharArray();
            int len = c.length;
            boolean[][] p = new boolean[len][len];
            for (int i = 0; i < len; i++)
                for (int j = 0; j < len - i; j++)
                    p[j][j + i] = c[j] == c[j + i] && (i <= 1 || p[j + 1][j + i - 1]);
            
            List<String> path = new ArrayList();
            List<List<String>> ans = new ArrayList();
            printout(0, s, p, path, ans);
            return ans;
        }
        
        private void printout(int pos, String s, boolean[][] p, List<String> path, List<List<String>> ans) {
            if (pos >= s.length()) {
                ans.add(new ArrayList(path));
                return;
            }
            
            for (int i = pos; i < s.length(); i++)
                if (p[pos][i]) {
                    path.add(s.substring(pos, i + 1));
                    printout(i + 1, s, p, path, ans);
                    path.remove(path.size() - 1);
                }
        }
    }

  • 0
    T

    Cool solution


  • 0
    H

    @ofLucas
    is the time complexity O(n^2)?


Log in to reply
 

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