有一個二維字符陣列和一個搜索詞。任務是找出陣列中是否有單詞。單詞可以以 4 個方向的任意曲線放置在陣列中：上、下、左、右。您不能重復使用這些字母。例如，從陣列[a, b, c]中你不能得到一個 word "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的時候，并且是單詞沒有完成并且沒有其他合適的字母來結束單詞的時候。
uj5u.com熱心網友回復：
您的問題似乎與：
for (let v of clear) {puzzle[v.y][v.x] = "-"}
clear.length = 0;
對于這個詞"angular"，這會將所有“a”設定為“-”，這是你不應該做的，你應該只在"a"使用它時設定為空白。目前，您正在將所有“a”字符設定為"-"這意味著您將無法"a"再次使用（因此不會找到a“angul a r”中的第二個字符）。
我建議洗掉你的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)轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/426868.html
標籤：javascript 递归
上一篇：這個函式如何處理2個串列？