Word Search II

Word Search II

20%

Accepted

Given a matrix of lower alphabets and a dictionary. Find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position. 

Have you met this question in a real interview?

Yes

Example

Given matrix:

doafagaidcan

and dictionary:

{"dog", "dad", "dgdg", "can", "again"}

return {"dog", "dad", "can", "again"}

dog:

doafagaidcan

dad:

doafagaidcan

can:

doafagaidcan

again:

doafagaidcan

Challenge

Using trie to implement your algorithm.

public class Solution {

    /**

     * @param board: A list of lists of character

     * @param words: A list of string

     * @return: A list of string

     */

   public ArrayList<String> wordSearchII(char[][] board, ArrayList<String> words) {

       // write your code here

  ArrayList<String> res = new ArrayList<String>();

  boolean[][] visited = new boolean[board.length][board[0].length];

  for(String word : words){

  boolean found = false;

  visited = new boolean[board.length][board[0].length];

  for(int i = 0; i < board.length; i++){

  for(int j = 0; j < board[0].length; j++){

  if(word.charAt(0) == board[i][j]){ 

  if(_dfs(board, word, visited, 0, i, j)){

  res.add(word);

  found = true;

  break;

  }

  }

  }

  if(found) break;

  }

}

return res;

  

   }

   

   private boolean _dfs(char[][] board, String word, boolean[][] visited, int start, int i, int j){

       if(start == word.length()){

  return true;

  }

  if(i < 0 || i >= visited.length || j < 0 || j >= visited[0].length || visited[i][j]) return false;

  

  if(word.charAt(start) != board[i][j]){

      return false;

  }

  visited[i][j] = true;

  boolean result = false;

  result = _dfs(board, word, visited, start+1, i+1, j);

  if(result == true){

       return result;

  }

  result = _dfs(board, word, visited, start+1, i-1, j);

   if(result == true){

       return result;

  }

  result = _dfs(board, word, visited, start+1, i, j+1);

   if(result == true){

       return result;

  }

  result = _dfs(board, word, visited, start+1, i, j-1);

  if(result == true){

       return result;

  }

  visited[i][j] = false;

  return false;

  

  

   }

}


public class Solution {
    /**
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
   Trie trie = new Trie();
   public ArrayList<String> wordSearchII(char[][] board, ArrayList<String> words) {
       // write your code here
  Set<String> res = new HashSet<String>();
  
  boolean[][] visited = new boolean[board.length][board[0].length];
 
  for(String word : words){
  trie.insert(word);
  }
  
  for(int i = 0; i < board.length; i++){
  for(int j = 0; j < board[0].length; j++){
  _dfs(res, board, i, j, visited, "");
  visited = new boolean[board.length][board[0].length];
  }
  }
  ArrayList<String> result = new ArrayList<String>(res);
  return result;
   }
   
   private void _dfs(Set<String> res, char[][] board, int i, int j, boolean[][] visited, String prefix){
  if(i < 0 || i >= visited.length || j < 0 || j >= visited[0].length || visited[i][j]) return;
 
  visited[i][j] = true;
  if(!trie.searchPrefix(prefix)){
      visited[i][j] = false;
      return;
  } 
  if(trie.search(prefix+board[i][j])){
  res.add(prefix+board[i][j]);
  }
  _dfs(res, board, i+1, j, visited, prefix+board[i][j]);
  _dfs(res, board, i-1, j, visited, prefix+board[i][j]);
  _dfs(res, board, i, j+1, visited, prefix+board[i][j]);
  _dfs(res, board, i, j-1, visited, prefix+board[i][j]);
  visited[i][j] = false;
  
  
   }
   
   
   class TrieNode{
  TrieNode[] children = new TrieNode[26];
  String item;
   }
   class Trie{
  TrieNode root;
  public Trie(){
  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;
  } else node = node.children[c - 'a'];
  }
  return word.equals(node.item);
  }
  
  public boolean searchPrefix(String prefix){
  TrieNode node = root;
  for(char c : prefix.toCharArray()){
  if(node.children[c - 'a'] == null){
  return false;
  } else node = node.children[c - 'a'];
  }
  return true;
  }
   }

}