Leetcode 212 Word Search II

Leetcode 212 Word Search II

Edit Word Search II on GitHub


Naive Approach

The description of problem is :

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.

Now since you already worked out Leetcode 79 Word Search, you must be thinking about the naive approach: for each word run the same DFS process as previous, if found then add it into result set.

public List<String> findWords(char[][] board, String[] words) {
  ArrayList<String> result = new ArrayList<String>();
  int m = board.length;
  int n = board[0].length;
 
  for (String word : words) {
    boolean flag = false;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        char[][] newBoard = new char[m][n];
        for (int x = 0; x < m; x++)
          for (int y = 0; y < n; y++)
            newBoard[x][y] = board[x][y];
 
        if (dfs(newBoard, word, i, j, 0)) {
          flag = true;
        }
      }
    }
    if (flag) {
      result.add(word);
    }
  }
 
  return result;
}
 
public boolean dfs(char[][] board, String word, int i, int j, int k) {
  int m = board.length;
  int n = board[0].length;
 
  if (i < 0 || j < 0 || i >= m || j >= n || k > word.length() - 1) {
    return false;
  }
 
  if (board[i][j] == word.charAt(k)) {
    char temp = board[i][j];
    board[i][j] = '#';
 
    if (k == word.length() - 1) {
      return true;
    } else if (dfs(board, word, i - 1, j, k + 1)
        || dfs(board, word, i + 1, j, k + 1)
        || dfs(board, word, i, j - 1, k + 1)
        || dfs(board, word, i, j + 1, k + 1)) {
      board[i][j] = temp;
      return true;
    }
 
  } else {
    return false;
  }
 
  return false;
}

Well, this will work, if we don’t have performance demand. This naive approach won’t pass the performance test since we are doing the job too dumb.

 


Trie Approach

Now recall Leetcode 208 Implement Trie (Prefix Tree). Since we have the prefix tree, which is the most commonly used data structure for implementing dictionary, we could do much better.

We could construct a Trie for the set of Strings before DFS. Now, in the DFS process, if the temporary String we have already found is not in the Trie, it means no matter what we find in the following DFS, it won’t match any word in our dictionary.

Thus we can return earlier instead of running additional DFS. This is called pruning 😀

public class Solution {
    Set<String> result = new HashSet<String>(); 
 
    public List<String> findWords(char[][] board, String[] words) {
 
        Trie trie = new Trie();
        for(String word: words){
            trie.insert(word);
        }
 
        int m=board.length;
        int n=board[0].length;
 
        boolean[][] recordVisited = new boolean[m][n];
 
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
               wordSearch(board, recordVisited, "", i, j, trie);
            }
        }
 
        return new ArrayList<String>(result);
    }
 
    public boolean wordSearch(char[][] board, boolean[][] recordVisited, String str, int i, int j, Trie trie){
        int m=board.length;
        int n=board[0].length;
 
        if(i<0 || j<0||i>=m||j>=n){
            return false;
        }
 
        if(recordVisited[i][j])
            return false;
 
        str = str + board[i][j];
 
        if(!trie.startsWith(str))
            return false;
 
        if(trie.search(str)){
            result.add(str);
        }
 
        recordVisited[i][j]=true;
        boolean res = wordSearch(board, recordVisited, str, i-1, j, trie)  
                 || wordSearch(board, recordVisited, str, i+1, j, trie)   
                 || wordSearch(board, recordVisited, str, i, j+1, trie) 
                 || wordSearch(board, recordVisited, str, i, j-1, trie);   
         recordVisited[i][j] = false;  
         return res; 
    }
}

class TrieNode{
    public TrieNode[] children = new TrieNode[26];
    public String item = "";
}
 
//Trie
class Trie{
    public TrieNode root = new TrieNode();
 
    public void insert(String word){
        TrieNode node = root;
        for(char c: word.toCharArray()){
            if(node.children[c-'a']==null){
                node.children[c-'a']= new TrieNode();
            }
            node = node.children[c-'a'];
        }
        node.item = word;
    }
 
    public boolean search(String word){
        TrieNode node = root;
        for(char c: word.toCharArray()){
            if(node.children[c-'a']==null)
                return false;
            node = node.children[c-'a'];
        }
        if(node.item.equals(word)){
            return true;
        }else{
            return false;
        }
    }
 
    public boolean startsWith(String prefix){
        TrieNode node = root;
        for(char c: prefix.toCharArray()){
            if(node.children[c-'a']==null)
                return false;
            node = node.children[c-'a'];
        }
        return true;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *