JAVA Solution based on DP and Trie


  • 0
    B

    I used a backward Trie instead of the common Hashmap to store the WordDict. Theoretically, this could guarantee the runtime and reduce redundant comparison. However, I feel the major time cost here is caused by generating the output strings...

    Runtime is 24~25ms.

    public class Solution {
        
        // Node of the Trie
        public class Node {
            Node[] child;
            boolean isWord;
            
            public Node(){
                child = new Node[256];
            }
        }
        
        List<String> ret;
        String src;
        
        public List<String> wordBreak(String s, List<String> wordDict) {
            ret = new LinkedList<String>();
            if (s.length() == 0){
                ret.add(s);
                return ret;
            }
            src = s;
            
            // build the backward Trie
            Node root = new Node();
            for (String w : wordDict ){
                Node cur = root;
                for (int i = w.length() - 1; i >= 0; --i){
                    int c = (int)w.charAt(i);
                    if (cur.child[c] == null){
                        cur.child[c] = new Node();
                    }
                        cur = cur.child[c];
                }
                cur.isWord = true;
            }
            
            List<List<Integer>> table = new ArrayList<List<Integer>>(s.length());
            char[] ch = s.toCharArray();
            table.add(new ArrayList<Integer>());
            table.get(0).add(-1);
            
            // DP for all possible sequences
            for (int i = 0; i < s.length(); ++i){
                List<Integer> local = new ArrayList<Integer>();
                int k = i;
                Node cur = root;
                while (k >= 0 && cur != null){
                    cur = cur.child[(int)ch[k]];
                    if (cur != null && cur.isWord){
                        if (table.get(k).size() > 0){
                            local.add(k);
                        }
                    }
                    k--;
                }
                table.add(local);
            }
            LinkedList<Integer> hist = new LinkedList<Integer>();
            hist.addLast(s.length());
            
            // write all outputs
            gen(table, s.length(), hist);
            return ret;
        }
        
        public void gen(List<List<Integer>> table, int k, LinkedList<Integer> history){
            List<Integer> back = table.get(k);
            
            for (int b : back){
                if (b == 0){
                    // output string
                    int prev = 0;
                    StringBuilder sb = new StringBuilder();
                    for (int h : history){
                        sb.append(src.substring(prev, h));
                        sb.append(' ');
                        prev = h;
                    }
                    sb.setLength(sb.length() - 1);
                    ret.add(sb.toString());
                }else{
                    history.addFirst(b);
                    gen(table, b, history);
                    history.removeFirst();
                }
            }
        }
    }
    

Log in to reply
 

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