递归遍历Grid并在Array - JAVASCRIPT中返回结果
递归遍历Grid并在Array - JAVASCRIPT中返回结果
提问于 2022-05-19 07:06:01
我在为做递归的逻辑而挣扎。
对于下面的网格，我需要搜索一个单词并返回一个索引数组，如果它存在，则返回一个索引数组；如果不存在，则返回一个空数组[]。
单词可以在网格中的任何地方开始，并且连续的字母可以紧接在前面字母的右边，也可以在前面的字母的右边。
grid = [
['c', 'c', 'x', 't', 'i', 'b'],
['c', 'c', 'a', 't', 'n', 'i'],
['a', 'c', 'n', 'n', 't', 't'],
['t', 'c', 's', 'i', 'p', 't'],
['a', 'o', 'o', 'o', 'a', 'a'],
['o', 'a', 'a', 'a', 'o', 'o'],
['k', 'a', 'i', 'c', 'k', 'i'],
];
word = "catnip"
find_word_location(grid, word)
// OUTPUT [ (1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 4) ]到目前为止，这就是我所拥有的，但它不起作用。
function find_word_location (grid, word) {
const dfs = (i, j, wordIndex, res) => {
if (wordIndex == word.length) return;
if (
i > grid.length - 1 ||
j > grid[0].length - 1 ||
grid[i][j] !== word[wordIndex]
)
return;
if (grid[i][j] == word[wordIndex]) {
res.push(`(${i},${j})`);
grid[i][j] = "#";
}
dfs(i + 1, j, wordIndex + 1, res);
dfs(i, j + 1, wordIndex + 1, res);
grid[i][j] = word[wordIndex];
return res;
};
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] == word[0]) {
let result = dfs(i, j, 0, []);
return result;
}
}
}
return [];
}回答 2
Stack Overflow用户
回答已采纳
发布于 2022-05-19 08:50:24
其中一些问题：
- 在
dfs的初始调用之后，您的代码总是返回结果。这意味着，如果第一个字母匹配，则必须从该单元格开始匹配整个单词。但这不是真的。它可能在那里找不到匹配的地方，而在网格中可能还有其他地方，其中的第一个字母提供了一个完整的单词匹配。因此，这个return语句应该是有条件的(只有在成功的情况下)。
- --
res引用的数组只会增长。它永远不会缩小。意识到只有一个res数组--由存在于dfs执行上下文中的所有res变量引用。因此，所有的部分匹配(最终无法导致完全匹配)都被收集到其中，并一个接一个地连接起来。没有回溯适用于它。
我发现更优雅的做法是，实际上只在整个单词匹配时才开始构建数组，然后在退出递归调用时填充数组(而不是在深化递归的同时这样做)。
- --
dfs的递归调用完全忽略了这些调用返回的值，因此没有区分失败和成功。您需要检查第一次递归调用的结果，如果调用成功，甚至不应该进行第二次调用。
- 不是问题，但是
if (grid[i][j] == word[wordIndex]) {中的条件总是正确的，因为您已经在前面的if语句中测试了相反的条件。
下面是对代码的更正，也实现了我在第二点中表达的想法，即只在已知数组成功的情况下填充数组：
// No res argument. res will be populated "inside-out" via the return value
function find_word_location (grid, word) {
const dfs = (i, j, wordIndex) => {
if (wordIndex == word.length) return []; // Start a solution with this res
if (
i > grid.length - 1 ||
j > grid[0].length - 1 ||
grid[i][j] !== word[wordIndex]
)
return;
grid[i][j] = "#";
// Use the returned value
// and apply short-circuit to avoid useless second call
const res = dfs(i + 1, j, wordIndex + 1) || dfs(i, j + 1, wordIndex + 1);
grid[i][j] = word[wordIndex];
if (res) res.unshift([i, j]); // Extend the path we got from recursion
return res;
};
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] == word[0]) {
let result = dfs(i, j, 0, []);
if (result) return result; // conditionally
}
}
}
return [];
}
var grid = [
['c', 'c', 'x', 't', 'i', 'b'],
['c', 'c', 'a', 't', 'n', 'i'],
['a', 'c', 'n', 'n', 't', 't'],
['t', 'c', 's', 'i', 'p', 't'],
['a', 'o', 'o', 'o', 'a', 'a'],
['o', 'a', 'a', 'a', 'o', 'o'],
['k', 'a', 'i', 'c', 'k', 'i'],
];
var word = "catnip";
var result = find_word_location(grid, word);
console.log(result);
Stack Overflow用户
发布于 2022-05-19 10:17:01
这种方法不会将结果传递给递归调用。
该函数采用grid、word或word左边部分以及实际索引(默认值为零)。
在内部，首先要检查边界，才是出口条件。
然后对通缉的人物进行检查。
在它里面用新单词长度检查，没有实际字符，如果是空字符串，它会返回索引。
其余部分几乎相同，没有检查找到的指标和它们是否与实际项目相邻的部分。
大致上，获取子索引，检查是否有索引，并返回结果或与实际索引(字母匹配)或只是其余。
const
findWord = (grid, word, i = 0, j = 0) => {
const isAdjacent = (x, y) => x === i && y === j + 1 || x === i + 1 && y === j;
let sub;
if (i + 1 === grid.length || j + 1 === grid[i].length) return [];
if (grid[i][j] === word[0]) {
const w = word.slice(1);
if (!w.length) return [[i, j]];
sub = findWord(grid, w, i + 1, j);
if (sub.length && isAdjacent(...sub[0])) return [[i, j], ...sub];
sub = findWord(grid, w, i, j + 1);
if (sub.length && isAdjacent(...sub[0])) return [[i, j], ...sub];
}
sub = findWord(grid, word, i + 1, j);
if (sub.length) return sub;
sub = findWord(grid, word, i, j + 1);
if (sub.length) return sub;
return [];
},
grid = [['c', 'c', 'x', 't', 'i', 'b'], ['c', 'c', 'a', 't', 'n', 'i'], ['a', 'c', 'n', 'n', 't', 't'], ['t', 'c', 's', 'i', 'p', 't'], ['a', 'o', 'o', 'o', 'a', 'a'], ['o', 'a', 'a', 'a', 'o', 'o'], ['k', 'a', 'i', 'c', 'k', 'i']],
word = "catnip",
result = findWord(grid, word);
console.log(result.map(p => p.join('-')));.as-console-wrapper { max-height: 100% !important; top: 0; }
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/72300044
复制相关文章
相似问题
腾讯云开发者
