DP + BackTracking Java Solution without cache


  • 0
    M
        public List<String> wordBreak(String s, List<String> wordDict) {
            List<String> lists = new ArrayList<>();
            if (s == null || wordDict == null || s.length() == 0 || wordDict.size() == 0) return lists;
            Set<String> dic = new HashSet<>(wordDict);
            int n = s.length();
            boolean[] p = new boolean[n + 1];
            p[0] = true;
            boolean[][] pre = new boolean[n + 1][n + 1];
            pre[0][0] = true;
            for (int i = 1; i <= n; ++i) {
                for (int j = i; j >= 1; --j) {
                    if (p[j - 1] && dic.contains(s.substring(j - 1, i))) {
                        p[i] = true;
                        pre[i][j] = true;
                    }
                }
            }
            dfs(s, n, new LinkedList<String>(), pre, lists);
            return lists;
        }
        private void dfs(String s, int end, List<String> list, boolean[][] pre, List<String> lists) {
            if (end == 0) {
                List<String> row = new ArrayList<>();
                StringBuilder sb = new StringBuilder();
                for (String word : list) {
                    if (sb.length() > 0) sb.append(" ");
                    sb.append(word);
                }
                lists.add(sb.toString());
                return;
            }
            int n = s.length();
            for (int j = n; j > 0; --j) {
                if (pre[end][j]) {
                    list.add(0, s.substring(j - 1, end));
                    dfs(s, j - 1, list, pre, lists);
                    list.remove(0);
                }
            }
        }
    

Log in to reply
 

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