Java Trie + DFS recursive


  • 0
    J

    a little lengthy, but pretty routine stuff:

    public class Solution {

    public static void main (String[] args) {
    	Solution sol = new Solution();
    	sol.findWords(new char[][] {{'a', 'b'}, {'c', 'd'}}, new String[] {"ab","cb","ad","bd","ac","ca","da","bc","db","adcb","dabc","abb","acb"} );
    }
    
    public List<String> findWords(char[][] board, String[] words) {
        Set<String> set = new HashSet<String>();
        
        // Build trie first.
        Trie trie = new Trie();
        for (String word : words) { 
        	trie.insert(word);
    	}
        
       	int m = board.length;
    	int n = board[0].length;
    	for (int i = 0; i < m; i++) {
    		for (int j = 0; j < n; j++) {
    			String word = "";
    			findWordsHelper(set, board, i, j, word, trie);
    		}
    	}
    	return new ArrayList<String>(set);
    }
    
    
    private void findWordsHelper(Set<String> set, char[][] board, int i, int j, String word, Trie trie) {
        if (i < 0 || j < 0|| i >= board.length || j >= board[0].length) {
            return;
        }
        word += board[i][j];
    	if (!trie.startsWith(word)) {
    		//terminate the searching.
    		return;
    	} else {
    		if (trie.search(word)) {
    			//found a word complete on trie.
    			set.add(word);
    		}
    		char storeChar = board[i][j];
    		board[i][j] = '*'; //temporally remove the (i, j) char from the board.
    		findWordsHelper(set, board, i-1, j, word, trie);
    		findWordsHelper(set, board, i+1, j, word, trie);
    		findWordsHelper(set, board, i, j-1, word, trie);
    		findWordsHelper(set, board, i, j+1, word, trie);
    		board[i][j] = storeChar; //restore the char.
    	}
    	return;
    }
    
    public class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
            root.wordEnd = false;
        }
    
        public void insert(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                Character c = new Character(word.charAt(i));
                if (!node.childdren.containsKey(c)) {
                	node.childdren.put(c, new TrieNode());
                }
                node = node.childdren.get(c);
            }
            node.wordEnd = true;
        }
    
        public boolean search(String word) {
        	TrieNode node = root;
        	boolean found = true;
        	for (int i = 0; i < word.length(); i++) {
        		Character c = new Character(word.charAt(i));
        		if (!node.childdren.containsKey(c)) {
        			return false;
        		}
        		node = node.childdren.get(c);
        	}
        	return found && node.wordEnd;
        }
    
    	public boolean startsWith(String prefix) {
    		TrieNode node = root;
    		boolean found = true;
    		for (int i = 0; i < prefix.length(); i++) {
    			Character c = new Character(prefix.charAt(i));
    			if (!node.childdren.containsKey(c)) {
    				return false;
    			}
    			node = node.childdren.get(c);
    		}
    		return found;
    	}
    
    }
    
    public class TrieNode {
        Map<Character, TrieNode> childdren;
        boolean wordEnd;
        
        public TrieNode() {
            childdren = new HashMap<Character, TrieNode>();
            wordEnd = false;
        }
    }
    

    }


Log in to reply
 

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