212. Word Search II

[Tcdian]

212. Word Search II

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

Example

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"]

Note

• All inputs are consist of lowercase letters a-z.
• The values of words are distinct.

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function(board, words) {
    const dictionary = new Trie();
    for (let i = 0; i < words.length; i++) {
        dictionary.insert(words[i]);
    }

    const result = [];
    const path = [];
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            search(i, j, dictionary.root);
        }
    }
    return result;

    function search(x, y, patrol) {
        const letter = board[x][y];
        board[x][y] = '#';
        const direction = [-1, 0, 1, 0, -1];
        if (patrol.data[letter] !== undefined) {
            path.push(letter);
            const next = patrol.data[letter];
            if (next.isEnd) {
                result.push(path.join(''));
                next.isEnd = false;
            }
            for (let i = 0; i < 4; i++) {
                const directionX = x + direction[i];
                const directionY = y + direction[i + 1];
                if (
                    directionX >= 0 && directionX < board.length
                        && directionY >= 0 && directionY < board[0].length
                        && board[directionX][directionY] !== '#'
                ) {
                    search(directionX, directionY, next);
                }
            }
            path.pop();
        }
        board[x][y] = letter;
    }
};

function TrieNode() {
    this.data = Object.create(null);
    this.isEnd = false;
}

function Trie() {
    this.root = new TrieNode();
}

Trie.prototype.insert = function(word) {
    let patrol = this.root;
    for (let i = 0; i < word.length; i++) {
        patrol.data[word[i]] = patrol.data[word[i]] || new TrieNode();
        patrol = patrol.data[word[i]];
    }
    patrol.isEnd = true;
}

• TypeScript Solution

interface TrieNodeData {
    [properName: string]: TrieNode;
}

class TrieNode {
    public data: TrieNodeData;
    public isEnd: boolean;
    constructor() {
        this.data = Object.create(null);
        this.isEnd = false;
    }
}

class Trie {
    public root: TrieNode;
    constructor() {
        this.root = new TrieNode();
    }
    insert(word: string) {
        let patrol = this.root;
        for (let i = 0; i < word.length; i++) {
            patrol.data[word[i]] = patrol.data[word[i]] || new TrieNode();
            patrol = patrol.data[word[i]];
        }
        patrol.isEnd = true;
    }
}

function findWords(board: string[][], words: string[]): string[] {
    const dictionary = new Trie();
    for (let i = 0; i < words.length; i++) {
        dictionary.insert(words[i]);
    }

    const result: string[] = [];
    const path: string[] = [];
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            search(i, j, dictionary.root);
        }
    }
    return result;

    function search(x: number, y: number, patrol: TrieNode) {
        const letter = board[x][y];
        board[x][y] = '#';
        const direction = [-1, 0, 1, 0, -1];
        if (patrol.data[letter] !== undefined) {
            path.push(letter);
            const next = patrol.data[letter];
            if (next.isEnd) {
                result.push(path.join(''));
                next.isEnd = false;
            }
            for (let i = 0; i < 4; i++) {
                const directionX = x + direction[i];
                const directionY = y + direction[i + 1];
                if (
                    directionX >= 0 && directionX < board.length
                        && directionY >= 0 && directionY < board[0].length
                        && board[directionX][directionY] !== '#'
                ) {
                    search(directionX, directionY, next);
                }
            }
            path.pop();
        }
        board[x][y] = letter;
    }
};