我正在為進行遞回的邏輯而苦苦掙扎。
對于下面的網格，我需要搜索一個單詞并回傳一個索引陣列，如果它存在則形成該單詞，如果它不存在則回傳一個空陣列 []。
單詞可以在網格中的任何位置開始，連續的字母可以緊接在前一個字母的下方或緊鄰的右側。
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 [];
}
uj5u.com熱心網友回復：
一些問題：
dfs在您的代碼的初始呼叫后總是回傳結果。這意味著它假定如果第一個字母匹配，則必須從該單元格開始匹配整個單詞。但是這是錯誤的。它可能在那里找不到匹配項，而網格中可能還有其他地方的第一個字母確實給出了完整的單詞匹配。所以這個return陳述句應該是有條件的（只有在成功的時候）。參考的陣列
res只增長。它永遠不會縮小。意識到只有一個res陣列——被執行背景關系res中的所有變數參考。dfs因此，所有部分匹配（最終無法導致完整匹配）都被收集在其中，并一個接一個地連接起來。沒有應用回溯。我發現實際上只在整個單詞匹配后才開始構建一個陣列，然后在退出遞回呼叫時填充一個陣列（而不是在加深遞回時這樣做）更優雅。
的遞回呼叫
dfs完全忽略了這些呼叫回傳的值，因此沒有區分失敗和成功。您需要檢查第一次遞回呼叫的結果，如果成功，則甚至不應該進行第二次呼叫。沒問題，但條件
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);uj5u.com熱心網友回復：
這種方法不會將結果交給遞回呼叫。
該函式采用grid、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; }轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/478402.html
標籤：javascript 算法 递归
下一篇：謎題：相反顏色的兩個相鄰單元格