递归解决方案中错误的退出条件

Question

有一个二维字符数组和一个搜索词。任务是找出数组中是否有单词。单词可以放在数组中任意曲线，有4个方向：up, down, left ，对。您不能重复使用这些字母。例如，从数组 [a, b, c] 中，您无法得到单词 "ababc"。请参阅下面的示例。

function findWord(puzzle, word) {
  
}

const puzzle = [
  'ANGULAR',
  'REDNCAE',
  'RFIDTCL',
  'AGNEGSA',
  'YTIRTSP',
];

console.log(findWord(puzzle, 'ANGULAR')); // true
console.log(findWord(puzzle, 'REACT')); // true
console.log(findWord(puzzle, 'ARRAY')); // true
console.log(findWord(puzzle, 'UNDEFINED')); // true
console.log(findWord(puzzle, 'RED')); // true
console.log(findWord(puzzle, 'STRING')); // true
console.log(findWord(puzzle, 'CLASS')); // true
console.log(findWord(puzzle, 'FUNCTION')); // false
console.log(findWord(puzzle, 'NULL')); // false

我的解决方案：

function findWord(puzzle, word) {
  puzzle = puzzle.map(e => e.split(""));
  const current = [];
  const clear = [];
  for (let y = 0; y < puzzle.length; y++) {
    for (let x = 0; x < puzzle[y].length; x++) {
      if (puzzle[y][x] === word[0]) {
        clear.push({x, y});        
        current.push(...getSurround(x, y, puzzle));
      }
    }
  }
  return nextTurn(puzzle, word.slice(1), clear, current);
}

function nextTurn(puzzle, word, clear, current) {
  const next = [];
  if (word.length === 0) return true;

  for (let v of clear) {puzzle[v.y][v.x] = "-"}
  clear.length = 0;

  for (let v of current) {
    if (v === null) continue;
    if (v.letter === word[0]) {
      clear.push({x: v.x, y: v.y});
      next.push(...getSurround(v.x, v.y, puzzle));      
    }
  }
  if (next.length === 0) return false;
  return nextTurn(puzzle, word.slice(1), clear, next);
}

function getSurround(x, y, puzzle) {
  const surround = [];
  const u = (y !== 0) ? {x, y: y - 1, letter: puzzle[y - 1][x]} : null;
  const r = (x !== puzzle[y].length - 1) ? {x: x + 1, y, letter: puzzle[y][x + 1]} : null;
  const d = (y !== puzzle.length - 1) ? {x, y: y + 1, letter: puzzle[y + 1][x]} : null;
  const l = (x !== 0) ? {x: x - 1, y, letter: puzzle[y][x - 1]} : null;
  surround.push(u, r, d, l);
  return surround;
}

看起来解决方案可以找到这个词，但问题出在递归出口。我猜想，true是这个词完成的时候，false是这个词没有完成的时候，没有其他合适的字母来结束这个词。

Answer 1

您的问题似乎与：

for (let v of clear) {puzzle[v.y][v.x] = "-"}
clear.length = 0;

对于单词 "angular"，这会将所有“a”设置为“-”，您不应该这样做，您应该只将 "a" 设置为空白 if/when 你用它。当前，您将所有“a”字符设置为 "-"，这意味着您将无法再次使用 "a"（因此“angula[中的第二个 ar" 不会被发现。

我建议删除 clear 数组的想法，而是更新 nextTurn 函数：

function nextTurn(puzzle, word, current) {
  if (word.length === 0) return true;

  for (const v of current) {
    if (v.letter === word[0]) {
      const nextCandidates = getSurround(v.x, v.y, puzzle);
      puzzle[v.y][v.x] = '-'; // mark letter as we're using it
      const turnResult = nextTurn(puzzle, word.slice(1), nextCandidates);
      if(turnResult) // recursive call returned true
        return turnResult;
      // If using the letter at x,y didn't work, "un-mark" it
      puzzle[v.y][v.x] = v.letter;
    }
  }
  
  return false;
}

想法是在我们递归并调用 nextTurn() 之前将当前字母标记为“已使用”("-")。这允许我们在下次调用 nextTurn() 时搜索其周围字母之前使用当前字母。如果搜索该特定字母不起作用，我们回溯并将拼图中的字母设置回“可用”，方法是将字母设置回其原始值，以便我们可以搜索其他可能的选项（并可能在某些时候重复使用该字母进一步指出这个词）。

在下面的代码片段中，我还更新了您的 findWord() 函数，以便它将您的二维拼图字母数组转换为顶点数组（{x, y, letter} 对象），然后可以使用通过 nextTurn() 来计算每个字母的下一个可能的解决方案。最后，我还更新了您的 getSurround 函数以避免出现不需要的 null 值。这有助于消除对您知道不会处理的值的迭代：

function findWord(puzzle, word) {
  puzzle = puzzle.map(str => Array.from(str));
  const candidates = puzzle.flatMap((row, y) => row.map((letter, x) => toVertex(x, y, letter)));
  return nextTurn(puzzle, word, candidates);
}

function nextTurn(puzzle, word, current) {
  if (word.length === 0) return true;

  for (const v of current) {
    if (v.letter === word[0]) {
      const nextCandidates = getSurround(v.x, v.y, puzzle);
      //console.log(v.y, v.x, puzzle[v.y]);
      puzzle[v.y][v.x] = '-'; // mark letter as we're using it
      const turnResult = nextTurn(puzzle, word.slice(1), nextCandidates);
      if(turnResult) // recursive call returned true
        return turnResult;
      // If using the letter at x,y didn't work, "un-mark" it
      puzzle[v.y][v.x] = v.letter;
    }
  }
  
  return false;
}

function getSurround(x, y, puzzle) {
  const surround = [];
  if(y !== 0)
    surround.push(toVertex(x, y-1, puzzle[y - 1][x]));
    
  if(x !== puzzle[y].length - 1)
    surround.push(toVertex(x+1, y, puzzle[y][x + 1]));
    
  if(y !== puzzle.length - 1)
    surround.push(toVertex(x, y+1, puzzle[y + 1][x]));
    
  if(x !== 0)
    surround.push(toVertex(x - 1, y, puzzle[y][x - 1]));
    
  return surround;
}

function toVertex(x, y, letter) {
  return {x, y, letter};
}

const puzzle = [
  'ANGULAR',
  'REDNCAE',
  'RFIDTCL',
  'AGNEGSA',
  'YTIRTSP',
];

console.log('ANGULAR', findWord(puzzle, 'ANGULAR')); // true
console.log('REACT', findWord(puzzle, 'REACT')); // true
console.log('ARRAY', findWord(puzzle, 'ARRAY')); // true
console.log('UNDEFINED', findWord(puzzle, 'UNDEFINED')); // true
console.log('RED', findWord(puzzle, 'RED')); // true
console.log('STRING', findWord(puzzle, 'STRING')); // true
console.log('CLASS', findWord(puzzle, 'CLASS')); // true
console.log('FUNCTION', findWord(puzzle, 'FUNCTION')); // false
console.log('NULL', findWord(puzzle, 'NULL')); // false
console.log('RANER', findWord(puzzle, 'RANER')); // false (additional test to try re-use)

递归解决方案中错误的退出条件

Wrong exit condition in recursive solution

javascript

recursion