x 212. Word Search II

Word Search II - LeetCodeLeetCode

Should be able to implement Trie with below

Java

Javascript

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

let dict;
let answer;
var findWords = function (board, words) {

    const visited = new Array(board.length);
    for (let i = 0; i < board.length; i++) {
        visited[i] = new Array(board[0].length).fill(0);
    }

    dict = new Trie();
    dict.insertAll(words);

    answer = new Set();
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            const hasWord = checkWord(board, visited, i, j);
        }
    }

    return [...answer];
};

function checkWord(board, visited, row = 0, col = 0, word = []) {
    if (row < 0 || col < 0) return false;
    if (row >= board.length || col >= board[0].length) return false;
    if (visited[row][col] === 1) return false;

    const c = board[row][col];
    word = [...word, ...c];
    const [hasPrefix, done] = dict.startsWith(word);
    // console.log({
    //     c,
    //     word,
    //     hasPrefix,
    //     done
    // })

    if (!hasPrefix) return false;
    if (done === true) {
        answer.add(word.join(''));
    }


    visited[row][col] = 1;

    const up = checkWord(board, visited, row - 1, col, word);
    const down = checkWord(board, visited, row + 1, col, word);
    const right = checkWord(board, visited, row, col + 1, word);
    const left = checkWord(board, visited, row, col - 1, word);

    visited[row][col] = 0;
    return up || down || right || left;
}

const ALPHABET_SIZE = 26;
class TrieNode {

    constructor(parent, val, level = 0) {
        this.parent = parent;
        this.val = val;
        this.level = level;
        this.children = new Array(ALPHABET_SIZE).fill(null);
    }

}

class Trie {

    constructor(root) {
        this.root = root ?? new TrieNode(null);
        this.isEndOfWord = false;
    }

    insert(s) {
        let currentNode = this.root;

        let idx;
        for (let i = 0; i < s.length; i++) {
            const c = s[i];

            idx = c.charCodeAt() - 'a'.charCodeAt();
            if (currentNode.children[idx] === null) {
                currentNode.children[idx] = new TrieNode(currentNode, c, currentNode.level + 1);
            }

            currentNode = currentNode.children[idx];
        }

        currentNode.isEndOfWord = true;
    }

    search(s) {
        let currentNode = this.root;

        let idx;
        for (let i = 0; i < s.length; i++) {
            const c = s[i];
            idx = c.charCodeAt() - 'a'.charCodeAt();
            if (currentNode.children[idx] == null)
                return false;
            currentNode = currentNode.children[idx];
        }

        return currentNode.isEndOfWord;
    }

    startsWith(s) {
        let currentNode = this.root;

        let idx;
        for (let i = 0; i < s.length; i++) {
            const c = s[i];
            idx = c.charCodeAt() - 'a'.charCodeAt();
            if (currentNode.children[idx] == null)
                return [false, currentNode.isEndOfWord];
            currentNode = currentNode.children[idx];
        }

        return [true, currentNode.isEndOfWord];
    }

    insertAll(arr) {
        for (const s of arr) {
            this.insert(s);
        }
    }


}