My java solution using a trie


  • 0
    D
    class DisposibleTrieNode {
    // Initialize your data structure here.
    private DisposibleTrieNode[] subs;
    private boolean isSearchEnd;
    private DisposibleTrieNode parent;
    private int subCount;
    private char value;
    public DisposibleTrieNode(DisposibleTrieNode parent) {
    	subs = new DisposibleTrieNode[26];
    	isSearchEnd = false;
    	this.parent = parent;
    	this.subCount = 0;
    }
    public void setSearchEnd(boolean isSearchEnd) {
    	this.isSearchEnd = isSearchEnd;
    }
    public boolean isSearchEnd() {
    	return isSearchEnd;
    }
    public boolean isEmpty() {
    	return subCount == 0;
    }
    public DisposibleTrieNode getSub(char c) {
    	return subs[c - 'a'];
    }
    public DisposibleTrieNode makeSub(char c) {
    	int index = c - 'a';
    	if(subs[index] == null) {
    		subs[index] = new DisposibleTrieNode(this);
    		subs[index].setValue(c);
    		subCount++;
    	}
    	return subs[index];
    }
    public void removeSub(char c) {
    	DisposibleTrieNode sub = subs[c - 'a'];
    	if(sub != null) {
    		subs[c - 'a'] = null;
    		subCount--;
    		if(subCount == 0) {
    			destroy();
    		}
    	}
    }
    public void destroy() {
    	this.setSearchEnd(false);
    	if(this.subCount == 0 && this.parent != null) {
    		this.parent.removeSub(this.value);
    	}
    }
    public char getValue() {
    	return value;
    }
    public void setValue(char value) {
    	this.value = value;
    }
    

    }

    public class Solution {
    private static void insert(DisposibleTrieNode root, String word) {
    	int l = word.length();
        if(l == 0) {
        	return;
        }
        DisposibleTrieNode last = root;
        for(int i = 0; i < l; i++) {
        	last = last.makeSub(word.charAt(i));
        }
        last.setSearchEnd(true);
    }
    private void match(char[][] board, boolean[][] visited, DisposibleTrieNode node, int rows, int cols, int row, int col, StringBuilder prefix, List<String> result) {
    	prefix.append(node.getValue());
    	if(node.isSearchEnd()) {
    		result.add(prefix.toString());
    		node.destroy();
    	}
    	visited[row][col] = true;
    	int l = prefix.length();
    	if(row > 0 && !visited[row - 1][col] && node.getSub(board[row - 1][col]) != null) {
    		match(board, visited, node.getSub(board[row - 1][col]), rows, cols, row - 1, col, prefix, result);
    	}
    	if(col > 0 && !visited[row][col - 1] && node.getSub(board[row][col - 1]) != null) {
    		match(board, visited, node.getSub(board[row][col - 1]), rows, cols, row, col - 1, prefix, result);
    	}
    	if(row < rows - 1 && !visited[row + 1][col] && node.getSub(board[row + 1][col]) != null) {
    		match(board, visited, node.getSub(board[row + 1][col]), rows, cols, row + 1, col, prefix, result);
    	}
    	if(col < cols - 1 && !visited[row][col + 1] && node.getSub(board[row][col + 1]) != null) {
    		match(board, visited, node.getSub(board[row][col + 1]), rows, cols, row, col + 1, prefix, result);
    	}
    	prefix.deleteCharAt(prefix.length() - 1);
    	visited[row][col] = false;
    }
    public List<String> findWords(char[][] board, String[] words) {
    	DisposibleTrieNode root = new DisposibleTrieNode(null);
    	for(String word : words) {
    		insert(root, word);
    	}
    	int rows = board.length;
    	int cols = board[0].length;
    	boolean[][] visited = new boolean[rows][cols];
    	List<String> result = new ArrayList<String>();
    	if(rows * cols > words.length) {
    		Map<Character, Set<Integer>> map = new HashMap<Character, Set<Integer>>();
            int n = 0;
            for(int i = 0; i < rows; i++) {
            	for(int j = 0; j < cols; j++) {
            		char c = board[i][j];
            		if(map.containsKey(c)) {
            			map.get(c).add(n);
            		} else {
            			Set<Integer> set = new HashSet<Integer>();
            			set.add(n);
            			map.put(c, set);
            		}
            		n++;
            	}
            }
    		for(char c = 'a'; c <= 'z'; c++) {
    			if(root.getSub(c) != null && map.containsKey(c)) {
    				for(int position : map.get(c)) {
    					if(root.getSub(c) != null) {
    						int row = position / cols;
    						int col = position % cols;
    						match(board, visited, root.getSub(c), rows, cols, row, col, new StringBuilder(), result);
    					} else {
    						break;
    					}
    				}
    			}
    		}
    	} else {
    		for(int row = 0; row < rows; row++) {
    			for(int col = 0; col < cols; col++) {
    				char c = board[row][col];
    				if(root.getSub(c) != null) {
    					match(board, visited, root.getSub(c), rows, cols, row, col, new StringBuilder(), result);
    				}
    			}
    		}
    	}
    	return result;
    }
    

    }

    Lessons learned:

    1. Simple data structures like arrays are always faster than
      complicated template implementations like sets and maps. In this
      case use boolean[][] instead of set to store visited cells, use trie
      instead of map to categorize strings that share the same prefix.
    2. String concatenation can consume lots of time, use StringBuilder if
      possible.
    3. Avoid repeated computation as much as possible, in this case dispose
      string in a tree once the string is found (DisposibleTrieNode, I
      actually destruct the branch in a tree once all strings in the
      branch are found).
    4. Question field and answer field, if one has to be traversed to find
      answers, try to traverse the smaller one whichever it is for
      performance sake, in this case compare the board and words size to
      decide how the search should be carried out.

Log in to reply
 

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