Wednesday, September 2, 2015

Leetcode: Word search II

Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
For example,
Given words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
Return ["eat","oath"].
Note:
You may assume that all inputs are consist of lowercase letters a-z.
You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?
If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.
A time limit exceed solution:
Use a trie to save the word which does not in the board. So each time for a new word, we first search if the prefix exist in the trie. If yes, no need to search the board again. 
Simply put, the trie stores the prefix which does not exist in the board, so we don't need to waste of time to search again and again. 

Code (Java):
public class Solution {
    private int rows;
    private int cols;
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<String>();
        if (board == null || board.length == 0 || words == null || words.length == 0) {
            return result;
        } 
        
        Set<String> set = new HashSet<String>();
        
        Trie trie = new Trie();
        
        this.rows = board.length;
        this.cols = board[0].length;
        
        for (String word : words) {
            if (trie.searchPrefix(word) == false) {
                if (searchBoard(board, word)) {
                    if (!set.contains(word)) {
                        set.add(word);
                    }
                } else {
                    trie.insert(word);
                }
            } else {
                trie.insert(word);
            }
        }
        
        return new ArrayList<String>(set);
    }
    
    private boolean searchBoard(char[][] board, String word) {
        boolean[][] visited = new boolean[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (searchBoardHelper(board, i, j, word, 0, visited)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean searchBoardHelper(char[][] board, int row, int col, String word, int index, boolean[][] visited) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return false;
        }
        
        if (visited[row][col]) {
            return false;
        }
        
        if (board[row][col] != word.charAt(index)) {
            return false;
        }
        
        visited[row][col] = true;
        
        if (index == word.length() - 1 && board[row][col] == word.charAt(index)) {
            return true;
        }
        
        boolean ret; 
        ret = searchBoardHelper(board, row - 1, col, word, index + 1, visited) ||
              searchBoardHelper(board, row + 1, col, word, index + 1, visited) ||
              searchBoardHelper(board, row, col - 1, word, index + 1, visited) ||
              searchBoardHelper(board, row, col + 1, word, index + 1, visited);
        
        visited[row][col] = false;
        
        return ret;
    }
    
    class Trie {
        private TrieNode root = new TrieNode();
        
        // Insert a word
        void insert(String s) {
            TrieNode curr = root;
            int offset = 'a';
            for (int i = 0; i < s.length(); i++) {
                char character = s.charAt(i);
                if (curr.children[character - offset] == null) {
                    curr.children[character - offset] = 
                        new TrieNode(character, i == s.length() - 1 ? true : false);
                } else {
                    if (i == s.length() - 1) {
                        curr.children[character - offset].leaf = true;
                    }
                }
                curr = curr.children[character - offset];
            }
        }
        
        // Search for prefix
        boolean searchPrefix(String s) {
            TrieNode curr = root;
            int offset = 'a';
            for (int i = 0; i < s.length(); i++) {
                char character = s.charAt(i);
                if (curr.children[character - offset] == null) {
                    return false;
                } else if (curr.children[character - offset] != null && curr.children[character - offset].leaf) {
                    return true;
                }
                
                curr = curr.children[character - offset];
            }
            
            return false;
        }
    }
    
    class TrieNode {
        char val;
        boolean leaf;
        TrieNode[] children;
        
        public TrieNode() {
            this.val = '\0';
            this.children = new TrieNode[26];
        } 
        
        public TrieNode(char val, boolean leaf) {
            this.val = val;
            this.leaf = leaf;
            this.children = new TrieNode[26];
        }
    }
}

Code (Java):
public class Solution {
    private int rows;
    private int cols;
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<String>();
        if (board == null || board.length == 0 || words == null || words.length == 0) {
            return result;
        } 
        
        Set<String> set = new HashSet<String>();
        
        Trie trie = new Trie();
        
        this.rows = board.length;
        this.cols = board[0].length;
        
        // Step 1: insert all words into a trie
        for (String word : words) {
            trie.insert(word);
        }
        
        // Step 2: search the board
        boolean[][] visited = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                searchBoardHelper(board, i, j, "", visited, trie, set);
            }
        }
        
        return new ArrayList<String>(set);
    }
    
    
    private void searchBoardHelper(char[][] board, int row, int col, String word, 
                                      boolean[][] visited, Trie trie, Set<String> set) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return;
        }
        
        if (visited[row][col]) {
            return;
        }
        
        word += board[row][col];
        
        if (!trie.searchPrefix(word)) {
            return;
        }
        
        if (trie.search(word)) {
            set.add(word);
        }
        
        visited[row][col] = true;
        
        searchBoardHelper(board, row - 1, col, word, visited, trie, set);
        searchBoardHelper(board, row + 1, col, word, visited, trie, set);
        searchBoardHelper(board, row, col - 1, word, visited, trie, set);
        searchBoardHelper(board, row, col + 1, word, visited, trie, set);
        
        visited[row][col] = false;
    }
    
    class Trie {
        private TrieNode root = new TrieNode();
        
        // Insert a word
        void insert(String s) {
            TrieNode curr = root;
            int offset = 'a';
            for (int i = 0; i < s.length(); i++) {
                char character = s.charAt(i);
                if (curr.children[character - offset] == null) {
                    curr.children[character - offset] = 
                        new TrieNode(character, i == s.length() - 1 ? true : false);
                } else {
                    if (i == s.length() - 1) {
                        curr.children[character - offset].leaf = true;
                    }
                }
                curr = curr.children[character - offset];
            }
        }
        
        
        // Search a word
        boolean search(String s) {
            TrieNode curr = root;
            int offset = 'a';
            for (int i = 0; i < s.length(); i++) {
                char character = s.charAt(i);
                if (curr.children[character - offset] == null) {
                    return false;
                }
                curr = curr.children[character - offset];
            }
            
            if (curr != null && !curr.leaf) {
                return false;
            }
            
            return true;
        }
        
        // Search for prefix
        boolean searchPrefix(String s) {
            TrieNode curr = root;
            int offset = 'a';
            for (int i = 0; i < s.length(); i++) {
                char character = s.charAt(i);
                if (curr.children[character - offset] == null) {
                    return false;
                } 
                
                curr = curr.children[character - offset];
            }
            
            return true;
        }
    }
    
    class TrieNode {
        char val;
        boolean leaf;
        TrieNode[] children;
        
        public TrieNode() {
            this.val = '\0';
            this.children = new TrieNode[26];
        } 
        
        public TrieNode(char val, boolean leaf) {
            this.val = val;
            this.leaf = leaf;
            this.children = new TrieNode[26];
        }
    }
}

Analysis:
Let's think about the naive solution first. The naive solution is we search the board for each board. So for the dict with n words, and assume the ave. length of each word has length of m. Then without using a Trie, the time complexity would be O(n * rows * cols  * 4^m). 

Now let's analyze the time complexity of using a Trie. We put each word into the trie. Search in the Trie takes O(m) time, so the time complexity would be O(rows * cols * m * 4^m). Since mostly m << n, using a trie would save lots of time. 

No comments:

Post a Comment