递归遍历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 [];
}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
复制相关文章
相似问题
腾讯云开发者
