递归遍历网格并 Return 产生一个数组 - JAVASCRIPT

Question

我正在为执行递归的逻辑而苦苦挣扎。

对于下面的网格，我需要搜索一个词和 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"

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 [];
}

Answer 1

一些问题：

初次调用 dfs 您的代码后始终 return 结果。这意味着它假定如果第一个字母匹配，则整个单词必须从该单元格开始匹配。但是这是错误的。它可能在那里找不到匹配项，而网格中可能有其他地方的第一个字母 do 给出了完整的单词匹配。所以这个return语句应该是有条件的（只有当有成功的时候）。
res引用的数组只会增长。它从不收缩。意识到只有 one res 数组——由 dfs 执行上下文中的所有 res 变量引用。所以所有部分匹配（最终无法导致完整匹配）都被收集在其中，并一个接一个地连接起来。没有对其应用回溯。

我发现实际上只在整个单词匹配时才开始构建数组，然后在从递归调用中填充数组（如反对在加深递归的同时这样做）。
dfs的递归调用完全忽略了那些调用return的值，因此不区分失败和成功。您需要检查第一次递归调用的结果，如果成功，则甚至不应该进行第二次。
没问题，但是 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);

Answer 2

这种方式不会将结果交给递归调用。

该函数采用 grid、word 或剩余单词部分，以及实际索引，默认值为零。

在内部，通过检查边界首先出现退出条件。

然后检查所需字符。

在里面检查新单词长度，没有实际字符，如果是空字符串，它 return 是索引。

其余部分几乎相同，但没有检查找到的索引以及它们是否与实际元素相邻的部分。

粗略地获取子索引，检查是否有索引，然后 return 结果是使用实际索引（字母匹配）还是仅使用其余索引。

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; }

递归遍历网格并 Return 产生一个数组 - JAVASCRIPT

Recursively Iterate through Grid and Return Result in an Array - JAVASCRIPT

javascript

algorithm

recursion