Trie and DP when dictionary is given as a list of words


  • 0
    P
    public class Solution {
        public static class Trie {
            TrieNode wordT = new TrieNode();
            public void addWord(String word) {
                TrieNode node = wordT;
                HashMap<Character, TrieNode> child = node.children;
                
                for(int i = 0; i < word.length(); i++) {
                    char ch = word.charAt(i);
                    if(child.containsKey(ch)) {
                        node = child.get(ch);    
                    } else {
                        node = new TrieNode();
                        child.put(ch, node);
                    }
                    child = node.children;
                }
                node.isLeaf = true;
            }
            
            public boolean startsWith(String word) {
                TrieNode node = wordT;
                
                HashMap<Character, TrieNode> child = node.children;
                
                for(int i = 0; i < word.length(); i++) {
                    char ch = word.charAt(i);
                    if(child.containsKey(ch)) {
                        node = child.get(ch);    
                    } else {
                        return false;
                    }
                    child = node.children;
                }
                
                return true;
            }
            
            public boolean hasWord(String word) {
                TrieNode node = wordT;
                
                HashMap<Character, TrieNode> child = node.children;
                
                for(int i = 0; i < word.length(); i++) {
                    char ch = word.charAt(i);
                    if(child.containsKey(ch)) {
                        node = child.get(ch);    
                    } else {
                        return false;
                    }
                    child = node.children;
                }
                
                return node.isLeaf;
            }
        }
        
        public static class TrieNode {
            boolean isLeaf;
            HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
        }
        
        public boolean wordBreak(String s, List<String> wordDict) {
                Trie dict = new Trie();
                for(int i = 0; i < wordDict.size(); i++) {
                    dict.addWord(wordDict.get(i));
                }
                
                int[] pos = new int[s.length()+1];
                
                Arrays.fill(pos, -1);
                pos[0] = 0;
                
                for(int i = 0; i < s.length(); i++) {
                    if(pos[i] != -1) {
                        for(int j = i+1; j <= s.length(); j++) {
                            String str = s.substring(i,j);
                            if(dict.startsWith(str)) {
                                if(dict.hasWord(str)) {
                                    pos[j] = i;
                                }
                            } else {
                                break;
                            }
                        }
                    }
                }
                return pos[s.length()] != -1;
        }
    }
    

  • 0
    K

    @prasad3 Can you add time and space complexity for your solution?


Log in to reply
 

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