Open Tcdian opened 4 years ago
/**
* @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;
}
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;
}
};
212. Word Search II
给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
Example
Note
a-z
.words
are distinct.