Simple clean trie with DFS Java


  • 0
    J
    class Tnode{
        boolean isword;
        Tnode[] leaves;
        String s;
        public Tnode(String s){
            this.leaves=new Tnode[26];
            this.s=s;
        }
    }
    
    public class Solution {
        public List<String> findWords(char[][] board, String[] words) {
            List<String> res=new ArrayList<String>();
            if(board==null||board.length<1||board[0].length<1){
                return res;
            }
            int m=board.length;
            int n=board[0].length;
            boolean[][] visit=new boolean[m][n];
            Tnode root=new Tnode("");
            for(int i=0;i<words.length;i++){
                insert(words[i],root);
            }
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                   char c=board[i][j];
                   if(root.leaves[c-'a']!=null){
                       if(root.leaves[c-'a'].isword){
                           res.add(root.leaves[c-'a'].s);
                           root.leaves[c-'a'].isword=false;;
                       }
                       visit[i][j]=true;
                       search(board,i*n+j,root.leaves[c-'a'],res,visit);
                       visit[i][j]=false;
                   }
                }
            }
            return res;
            
        }
        
        public void insert(String s,Tnode root){
            Tnode cur=root;
            for(int i=0;i<s.length();i++){
                if(cur.leaves[s.charAt(i)-'a']==null){
                    cur.leaves[s.charAt(i)-'a']=new Tnode(s.substring(0,i+1));
                }
                if(i==s.length()-1){
                        cur.leaves[s.charAt(i)-'a'].isword=true;
                }
                cur=cur.leaves[s.charAt(i)-'a'];
            }
        }
        
        public void search(char[][] board, int pos, Tnode prev, List<String> res, boolean[][] visit){
            int m=board.length;
            int n=board[0].length;
            for(Integer connect:connected(board,visit,pos)){
                int x=connect/n;
                int y=connect%n;
                char c=board[x][y];
                if(prev.leaves[c-'a']!=null){
                    if(prev.leaves[c-'a'].isword){
                        res.add(prev.leaves[c-'a'].s);
                        prev.leaves[c-'a'].isword=false;
                    }
                    visit[x][y]=true;
                    search(board,connect,prev.leaves[c-'a'],res,visit);
                    visit[x][y]=false;
                }
            }
        }
        
        public List<Integer> connected(char[][] board, boolean[][] visit, int pos){
            List<Integer> res=new ArrayList<Integer>();
            int m=board.length;
            int n=board[0].length;
            int x=pos/n;
            int y=pos%n;
            for(int i=-1;i<=1;i+=2){
                if(x+i>=0&&x+i<m&&!visit[x+i][y]){
                    res.add((x+i)*n+y);
                }
                if(y+i>=0&&y+i<n&&!visit[x][y+i]){
                    res.add(x*n+y+i);
                }
            }
            return res;
        }
    }

  • 0
    S

    Hi, I have the following code which I think is similar to yours. But I keep getting TLE. Any ideas?

    Thanks much!

    public class Solution {
        private Trie vocab = null;
        private HashSet<String> words = null;
        
        public List<String> findWords(char[][] board, String[] wordList) {
            vocab = new Trie();
            for(int i = 0; i < wordList.length; i++)
                vocab.insert(wordList[i]);
                
            words = new HashSet<String>();
            
            boolean[][] visited = new boolean[board.length][board[0].length];
            for(int i = 0; i < board.length; i++)
                for(int j = 0; j < board[i].length; j++)
                    findWordsRecursive(board, i, j, new StringBuilder(board[i][j] + ""), visited);
                    
            return new ArrayList(words);
        }
        
        private void findWordsRecursive(char[][] board, int i, int j, StringBuilder sb, boolean[][] visited)
        {
            String temp = sb.toString();
            
            if(!vocab.startsWith(temp))
                return;
                
            // here, sb is guaranteed to be a prefix
            visited[i][j] = true;
            
            // first check if sb already is a valid word or not
            // if it is, add it to the list
            if(vocab.search(temp))
                words.add(temp);
                
            // go in all four directions if you can (ensuring that a visited cell is not visited again)
            
            // up
            if(i > 0 && !visited[i - 1][j])
                findWordsRecursive(board, i - 1, j, new StringBuilder(temp + board[i - 1][j]), visited);
                
            // down
            if(i < board.length - 1 && !visited[i + 1][j])
                findWordsRecursive(board, i + 1, j, new StringBuilder(temp + board[i + 1][j]), visited);
                
            // left
            if(j > 0 && !visited[i][j - 1])
                findWordsRecursive(board, i, j - 1, new StringBuilder(temp + board[i][j - 1]), visited);
                
            // right
            if(j < board[i].length - 1 && !visited[i][j + 1])
                findWordsRecursive(board, i, j + 1, new StringBuilder(temp + board[i][j + 1]), visited);
                
            visited[i][j] = false;
        }
        
        // make trie (prefix tree out of vocab)
        
        // iterate through board
        // at each cell, kick off a recursive thing
        
        // to pass to this recursive thing:
        //      a list of words thus far (to add to)
        //      current stringbuilder
        //      board and index of current cell
        
        // from within this recursive thing
        // go in all 4 directions (creating new copies of the string builder)
    }
    
    class TrieNode {
        // type of node:
        // 0 means root (contains no characters)
        // 1 means regular (contains character, non-ender)
        // 2 means ender (contains character, marks end of word)
        private int nodeType = 0;
        private char ch = '.';
        private HashMap<Character, TrieNode> children = null;
        
        // Initialize your data structure here.
        
        // constructor for root
        public TrieNode() {
            this(0, '.');
        }
        
        // constructor for other node types (types 1 and 2)
        public TrieNode(int nodeType, char ch)
        {
            children = new HashMap<Character, TrieNode>();
            this.nodeType = nodeType;
            this.ch = ch;
        }
        
        // get node type
        public int getNodeType()
        {
            return nodeType;
        }
        
        // update node type
        public void updateNodeType(int type)
        {
            nodeType = type;
        }
        
        // get character
        public char getChar()
        {
            return ch;
        }
        
        // get child correspoding to character (returns null if not present)
        public TrieNode getChildForChar(char ch)
        {
            return children.get(ch);
        }
        
        // add child 
        public void addChild(TrieNode t)
        {
            children.put(t.getChar(), t);
        }
    }
    
    class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            // search first, if word exists then just return
            if(search(word))
                return;
                
            TrieNode temp = root;
            for(int i = 0; i < word.length(); i++)
            {
                if(temp.getChildForChar(word.charAt(i)) == null)
                    temp.addChild(new TrieNode(1, word.charAt(i)));
                        
                temp = temp.getChildForChar(word.charAt(i));
                
                if(i == word.length() - 1)
                    temp.updateNodeType(2);
            }
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            TrieNode temp = root;
            for(int i = 0; i < word.length() && temp.getChildForChar(word.charAt(i)) != null; i++)
            {
                temp = temp.getChildForChar(word.charAt(i));
                
                if(i == word.length() - 1 && temp.getNodeType() == 2)
                    return true;
            }
            
            return false;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            TrieNode temp = root;
            
            for(int i = 0; i < prefix.length(); i++)
            {
                temp = temp.getChildForChar(prefix.charAt(i));
                
                if(temp == null)
                    return false;
            }
            
            return true;
        }
    }

Log in to reply
 

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