无法使用 'in' 运算符在未定义中搜索 'd'
Cannot use 'in' operator to search for 'd' in undefined
我正在尝试使用实现 trie 的深度优先搜索算法在 JavaScript 中编写一个难以解决的问题。构建 trie 时,我没有收到任何错误;然而,当 trie 到达 dfs 算法时,它给我“类型:错误,不能使用 'in' 运算符在未定义中搜索 'd'。
我无法确定问题出在我的 generate_trie 函数还是我的 depth_first_search 算法。您可以在下面找到该程序的所有代码。
// Sample Boggle Dictionary
var boggle_dxctionary = ['apple', 'pickle', 'side',
'sick', 'mood', 'cat',
'cats', 'man', 'super',
'antman', 'godzilla', 'dog',
'dot', 'sine', 'cos',
'signal', 'bitcoin', 'cool',
'kick', 'zapper'
];
// Sample Boggle Board
var boggle_board = [
['c', 'n', 't', ],
['d', 'a', 't', ],
['o', 'o', 'm', ],
];
var column_length = boggle_board[0].length;
var row_length = boggle_board.length;
var trie_node = {
'valid': false,
'next': {}
};
var neighbors_delta = [
[-1, -1],
[-1, 0],
[-1, 1],
[0, -1],
[0, 1],
[1, -1],
[1, 0],
[1, 1],
];
function generate_trie(word, node) {
if (!(word)) {
return;
}
if ((word[0] in node) == false) {
node[word[0]] = {
'valid': (word.length == 1),
'next': {}
};
}
generate_trie(word.slice(1, ), node[word[0]]);
}
function build_trie(boggle_dxct, trie) {
for (word = 0; word < boggle_dxct.length; word++) {
generate_trie(boggle_dxct[word], trie);
}
return trie;
}
function get_neighbors(row, column) {
var neighbors = [];
for (neighbor = 0; neighbor < neighbors_delta.length; neighbor++) {
new_row = row + neighbors_delta[neighbor][0];
new_column = column + neighbors_delta[neighbor][1];
if (new_row >= row_length || new_column >= column_length || new_row < 0 || new_column < 0) {
continue;
}
neighbors.push([new_row, new_column]);
}
return neighbors;
}
function depth_first_search(row, column, visited, trie, current_word, found_words, board) {
var row_column_pair = [row, column];
console.log(row_column_pair);
if (row_column_pair in visited) {
return;
}
letter = board[row][column];
visited.push(row_column_pair);
console.log("Up to here is good3");
console.log(letter);
if (letter in trie) {
current_word = current_word + letter;
console.log("Up to here is good4");
if (trie[letter]['valid']) {
found_words.push(current_word);
}
neighbors = get_neighbors(row, column);
for (n = 0; n < neighbors.length; n++) {
console.log("Up to here is good5");
depth_first_search(neighbors[n][0], neighbors[n][1], visited.slice(0, visited.length), trie[letter], current_word, found_words, board);
console.log("Up to here is good6");
}
}
}
function main(trie_node, board) {
trie_node = build_trie(boggle_dxctionary, trie_node);
found_words = [];
for (r = 0; r < row_length; r++) {
console.log("Up to here is good1");
for (c = 0; c < column_length; c++) {
var visited = [];
var current_word = '';
depth_first_search(r, c, visited, trie_node, current_word, found_words, board);
console.log("Up to here is good2");
}
}
console.log(found_words);
}
main(trie_node,boggle_board);
问题是您没有在 depth_first_search
中将 letter
声明为局部变量。所以当它在for
循环中调用自己时,递归调用改变了letter
的值,而trie[letter]
没有找到任何东西。
始终 使用局部变量,除非您有特殊原因不这样做。我在下面的代码中添加了 var
声明。
// Sample Boggle Dictionary
var boggle_dxctionary = ['apple', 'pickle', 'side',
'sick', 'mood', 'cat',
'cats', 'man', 'super',
'antman', 'godzilla', 'dog',
'dot', 'sine', 'cos',
'signal', 'bitcoin', 'cool',
'kick', 'zapper'
];
// Sample Boggle Board
var boggle_board = [
['c', 'n', 't', ],
['d', 'a', 't', ],
['o', 'o', 'm', ],
];
var column_length = boggle_board[0].length;
var row_length = boggle_board.length;
var trie_node = {
'valid': false,
'next': {}
};
var neighbors_delta = [
[-1, -1],
[-1, 0],
[-1, 1],
[0, -1],
[0, 1],
[1, -1],
[1, 0],
[1, 1],
];
function generate_trie(word, node) {
if (!(word)) {
return;
}
if ((word[0] in node) == false) {
node[word[0]] = {
'valid': (word.length == 1),
'next': {}
};
}
generate_trie(word.slice(1, ), node[word[0]]);
}
function build_trie(boggle_dxct, trie) {
for (var word = 0; word < boggle_dxct.length; word++) {
generate_trie(boggle_dxct[word], trie);
}
return trie;
}
function get_neighbors(row, column) {
var neighbors = [];
for (var neighbor = 0; neighbor < neighbors_delta.length; neighbor++) {
var new_row = row + neighbors_delta[neighbor][0];
var new_column = column + neighbors_delta[neighbor][1];
if (new_row >= row_length || new_column >= column_length || new_row < 0 || new_column < 0) {
continue;
}
neighbors.push([new_row, new_column]);
}
return neighbors;
}
function depth_first_search(row, column, visited, trie, current_word, found_words, board) {
var row_column_pair = [row, column];
console.log(row_column_pair);
if (row_column_pair in visited) {
return;
}
var letter = board[row][column];
visited.push(row_column_pair);
console.log("Up to here is good3");
console.log(letter);
if (letter in trie) {
current_word = current_word + letter;
console.log("Up to here is good4");
if (trie[letter]['valid']) {
found_words.push(current_word);
}
var neighbors = get_neighbors(row, column);
for (n = 0; n < neighbors.length; n++) {
console.log("Up to here is good5");
depth_first_search(neighbors[n][0], neighbors[n][1], visited.slice(0, visited.length), trie[letter], current_word, found_words, board);
console.log("Up to here is good6");
}
}
}
function main(trie_node, board) {
trie_node = build_trie(boggle_dxctionary, trie_node);
var found_words = [];
for (r = 0; r < row_length; r++) {
console.log("Up to here is good1");
for (c = 0; c < column_length; c++) {
var visited = [];
var current_word = '';
depth_first_search(r, c, visited, trie_node, current_word, found_words, board);
console.log("Up to here is good2");
}
}
console.log(found_words);
}
main(trie_node, boggle_board);
我正在尝试使用实现 trie 的深度优先搜索算法在 JavaScript 中编写一个难以解决的问题。构建 trie 时,我没有收到任何错误;然而,当 trie 到达 dfs 算法时,它给我“类型:错误,不能使用 'in' 运算符在未定义中搜索 'd'。
我无法确定问题出在我的 generate_trie 函数还是我的 depth_first_search 算法。您可以在下面找到该程序的所有代码。
// Sample Boggle Dictionary
var boggle_dxctionary = ['apple', 'pickle', 'side',
'sick', 'mood', 'cat',
'cats', 'man', 'super',
'antman', 'godzilla', 'dog',
'dot', 'sine', 'cos',
'signal', 'bitcoin', 'cool',
'kick', 'zapper'
];
// Sample Boggle Board
var boggle_board = [
['c', 'n', 't', ],
['d', 'a', 't', ],
['o', 'o', 'm', ],
];
var column_length = boggle_board[0].length;
var row_length = boggle_board.length;
var trie_node = {
'valid': false,
'next': {}
};
var neighbors_delta = [
[-1, -1],
[-1, 0],
[-1, 1],
[0, -1],
[0, 1],
[1, -1],
[1, 0],
[1, 1],
];
function generate_trie(word, node) {
if (!(word)) {
return;
}
if ((word[0] in node) == false) {
node[word[0]] = {
'valid': (word.length == 1),
'next': {}
};
}
generate_trie(word.slice(1, ), node[word[0]]);
}
function build_trie(boggle_dxct, trie) {
for (word = 0; word < boggle_dxct.length; word++) {
generate_trie(boggle_dxct[word], trie);
}
return trie;
}
function get_neighbors(row, column) {
var neighbors = [];
for (neighbor = 0; neighbor < neighbors_delta.length; neighbor++) {
new_row = row + neighbors_delta[neighbor][0];
new_column = column + neighbors_delta[neighbor][1];
if (new_row >= row_length || new_column >= column_length || new_row < 0 || new_column < 0) {
continue;
}
neighbors.push([new_row, new_column]);
}
return neighbors;
}
function depth_first_search(row, column, visited, trie, current_word, found_words, board) {
var row_column_pair = [row, column];
console.log(row_column_pair);
if (row_column_pair in visited) {
return;
}
letter = board[row][column];
visited.push(row_column_pair);
console.log("Up to here is good3");
console.log(letter);
if (letter in trie) {
current_word = current_word + letter;
console.log("Up to here is good4");
if (trie[letter]['valid']) {
found_words.push(current_word);
}
neighbors = get_neighbors(row, column);
for (n = 0; n < neighbors.length; n++) {
console.log("Up to here is good5");
depth_first_search(neighbors[n][0], neighbors[n][1], visited.slice(0, visited.length), trie[letter], current_word, found_words, board);
console.log("Up to here is good6");
}
}
}
function main(trie_node, board) {
trie_node = build_trie(boggle_dxctionary, trie_node);
found_words = [];
for (r = 0; r < row_length; r++) {
console.log("Up to here is good1");
for (c = 0; c < column_length; c++) {
var visited = [];
var current_word = '';
depth_first_search(r, c, visited, trie_node, current_word, found_words, board);
console.log("Up to here is good2");
}
}
console.log(found_words);
}
main(trie_node,boggle_board);
问题是您没有在 depth_first_search
中将 letter
声明为局部变量。所以当它在for
循环中调用自己时,递归调用改变了letter
的值,而trie[letter]
没有找到任何东西。
始终 使用局部变量,除非您有特殊原因不这样做。我在下面的代码中添加了 var
声明。
// Sample Boggle Dictionary
var boggle_dxctionary = ['apple', 'pickle', 'side',
'sick', 'mood', 'cat',
'cats', 'man', 'super',
'antman', 'godzilla', 'dog',
'dot', 'sine', 'cos',
'signal', 'bitcoin', 'cool',
'kick', 'zapper'
];
// Sample Boggle Board
var boggle_board = [
['c', 'n', 't', ],
['d', 'a', 't', ],
['o', 'o', 'm', ],
];
var column_length = boggle_board[0].length;
var row_length = boggle_board.length;
var trie_node = {
'valid': false,
'next': {}
};
var neighbors_delta = [
[-1, -1],
[-1, 0],
[-1, 1],
[0, -1],
[0, 1],
[1, -1],
[1, 0],
[1, 1],
];
function generate_trie(word, node) {
if (!(word)) {
return;
}
if ((word[0] in node) == false) {
node[word[0]] = {
'valid': (word.length == 1),
'next': {}
};
}
generate_trie(word.slice(1, ), node[word[0]]);
}
function build_trie(boggle_dxct, trie) {
for (var word = 0; word < boggle_dxct.length; word++) {
generate_trie(boggle_dxct[word], trie);
}
return trie;
}
function get_neighbors(row, column) {
var neighbors = [];
for (var neighbor = 0; neighbor < neighbors_delta.length; neighbor++) {
var new_row = row + neighbors_delta[neighbor][0];
var new_column = column + neighbors_delta[neighbor][1];
if (new_row >= row_length || new_column >= column_length || new_row < 0 || new_column < 0) {
continue;
}
neighbors.push([new_row, new_column]);
}
return neighbors;
}
function depth_first_search(row, column, visited, trie, current_word, found_words, board) {
var row_column_pair = [row, column];
console.log(row_column_pair);
if (row_column_pair in visited) {
return;
}
var letter = board[row][column];
visited.push(row_column_pair);
console.log("Up to here is good3");
console.log(letter);
if (letter in trie) {
current_word = current_word + letter;
console.log("Up to here is good4");
if (trie[letter]['valid']) {
found_words.push(current_word);
}
var neighbors = get_neighbors(row, column);
for (n = 0; n < neighbors.length; n++) {
console.log("Up to here is good5");
depth_first_search(neighbors[n][0], neighbors[n][1], visited.slice(0, visited.length), trie[letter], current_word, found_words, board);
console.log("Up to here is good6");
}
}
}
function main(trie_node, board) {
trie_node = build_trie(boggle_dxctionary, trie_node);
var found_words = [];
for (r = 0; r < row_length; r++) {
console.log("Up to here is good1");
for (c = 0; c < column_length; c++) {
var visited = [];
var current_word = '';
depth_first_search(r, c, visited, trie_node, current_word, found_words, board);
console.log("Up to here is good2");
}
}
console.log(found_words);
}
main(trie_node, boggle_board);