递归解中的错误退出条件

Question

有一个2D字符数组和一个搜索词。任务是找出数组中是否有单词。这个词可以放置在任意曲线的数组中，有四个方向:上、下、左、右。你不能再用字母了。例如，从数组[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”设置为“to "-"，如果/当您使用它时，您只应该将"a"设置为空。目前，您正在将所有"a“字符设置为"-"，这意味着您将无法再次使用"a" (因此将找不到”安圭拉ar“中的第二个a )。

我建议删除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;
}

这样做的目的是将当前的字母标记为"used“("-")，然后再恢复并调用nextTurn()。这允许我们在下一次调用nextTurn()时搜索其周围的字母之前直接使用当前的字母。如果搜索特定的字母不起作用，我们会将字谜中的字母返回到"available“，方法是将字母设置为原来的值，以便我们可以搜索其他可能的选项(并可能在单词的另一个点上重用该字母)。

在下面的片段中，我还更新了您的findWord()函数，以便它将您的2d拼图字母数组转换为一个顶点数组({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)

​