212. Word Search II

Word Search II

Problem Description 

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

 

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

 

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

Approach) Trie

• Create a trie with all the words 
• Iterate through every letter and run DFS if it's in the first layer of the trie 
• DFS backtracking

/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */

const endWord = '*'

class Trie{
    constructor(words){
        this.root = {}
        this.isWord = false
        words.forEach(word => this.addWord(word))
    }
    
    addWord(word){
        let current = this.root
        
        for(const letter of word){
            if(!current[letter]){
                current[letter] = {}
            }
            current = current[letter]   
        }
        current.isWord = true
    }
    
}


var findWords = function(board, words) {
    const trie = new Trie(words)
    const result = new Set()
    
    const visited = new Set()
    
    const dfs = (i, j, node, subResult) => {
        //base cases: out of bounds, letter does not exist in next prefix
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || !node[board[i][j]] || visited.has(`${i} ${j}`)){
            return
        }
        
        visited.add(`${i} ${j}`)
        subResult += board[i][j]
        
        node = node[board[i][j]]
        
        if(node.isWord){
            result.add(subResult)    
        }
        
        dfs(i, j+1, node, subResult)
        dfs(i, j-1, node, subResult)
        dfs(i-1, j, node, subResult)
        dfs(i+1, j, node, subResult)
        
        
        visited.delete(`${i} ${j}`)
        
    }
    
    for(let i = 0; i < board.length; i++){
        for(let j = 0; j < board[0].length; j++){
            if(trie.root[board[i][j]]){
                dfs(i, j, trie.root, "")
            }
        }
    }
    
    
    return [...result]

};

Approach) Intuitive

/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function(mat, words) {
   let m = mat.length;
   let n = mat[0].length;
   let dirs = [[-1,0], [1,0], [0,1], [0,-1]];
   let root = {};
    let result = [];
   
    // Insert all word using tries
    for(let word of words){
        let node = root;
        for(let c of word){ 
            if(!node[c]){
                node[c] = {};
            }
            node = node[c]
        }
        node['word'] = word
    }
    
    for(let i=0; i<m; i++){
        for(let j=0; j<n; j++){
            let val = mat[i][j];
            if(root[val]){
                searchWord(i,j,root[val])
            }
        }
    }
    return result
    
    function searchWord(i,j, node){
        if(node['word']){
            result.push(node['word'])
            node['word'] = null;

        }
        let temp = mat[i][j];
        mat[i][j] = '*';
        
        for(let dir of dirs){
            let x = dir[0] + i;
            let y = dir[1] + j;
            if(x >=0 && x<m && y>=0 && y<n && mat[x][y] !== '*' && node[mat[x][y]]  ){
                searchWord(x, y, node[mat[x][y]]) 
            }
            
        }
        mat[i][j] = temp;
    } 
};

Approach) Depth-First Search + Trie + Backtrack

var findWords = function (board, words) {
    const [R, C] = [board.length, board[0].length];
    const visit = new Array(R).fill(false).map(() => new Array(C).fill(false));
    const res = new Set();

    // Trie Implementation
    function TrieNode() {
        this.children = new Map();
        this.end = false;
    }
    // Init Trie
    const root = new TrieNode();

    function addWord(word) {
        let curr = root;
        for (let i = 0; i < word.length; i++) {
            const c = word[i];
            if (!curr.children.has(c)) curr.children.set(c, new TrieNode());
            curr = curr.children.get(c);
        }
        curr.end = true;
    }

    // Add all the word to trie
    for (let word of words) addWord(word);

    function dfs(r, c, trieNode, word) {
        if (r < 0 || c < 0 || r === R || c === C || visit[r][c] || !trieNode.children.get(board[r][c])) return;

        word = word + board[r][c];
        visit[r][c] = true;
        trieNode = trieNode.children.get(board[r][c]);
        if (trieNode.end) res.add(word);
        dfs(r + 1, c, trieNode, word);
        dfs(r - 1, c, trieNode, word);
        dfs(r, c + 1, trieNode, word);
        dfs(r, c - 1, trieNode, word);
        visit[r][c] = false;
    }

    for (let r = 0; r < R; r++) {
        for (let c = 0; c < C; c++) {
            dfs(r, c, root, '');
        }
    }
    return [...res];
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 212. Word Search II

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.