各位邦友好,敝人想問一下leetcode
https://leetcode.com/problems/word-search/
這是一道典型的DFS題,我用JavaScript寫的:
var exist = function(board, word) {
let row = board.length, col = board[0].length;
let dfs = (word, r, c) =>{
if (!word.length){
return true;
}
else if (r>=0 && r<row && c>=0 && c<col && word[0] == board[r][c]){
let tmp = board[r][c];
board[r][c] = '#';
if (dfs(word.substr(1), r+1, c) || dfs(word.substr(1), r-1, c) || dfs(word.substr(1), r, c+1) || word.substr(1), r, c-1){
return true;
}
board[r][c] = tmp;
return false;
}
else {
return false;
}
}
for (let r=0; r<row; r++){
for (let c=0; c<col; c++){
if (dfs(word, r, c)){
return true;
}
}
}
return false;
};
但是以下這個TEST CASE無法通過
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"ABCB"
我用Python寫,和上面JavaScript的程式相同的邏輯,就通過了
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
row = len(board)
col = len(board[0])
def dfs(word, r, c):
if not word:
return True
elif (r>=0 and r<row and c>=0 and c<col and board[r][c] == word[0]):
tmp = board[r][c]
board[r][c] = '#'
if (dfs(word[1:],r+1,c) or dfs(word[1:],r-1,c) or dfs(word[1:],r,c+1) or dfs(word[1:],r,c-1)):
return True
board[r][c] = tmp
else:
return False
for r in range(row):
for c in range(col):
if dfs(word, r, c):
return True
return False
敝人真的不知道自己的JavaScript程式碼錯在哪,也不懂該從何debug起
不知這裡有沒有高手願意提點,謝謝!
最後一個 word.substr(1)
沒包到 dfs
。 ((看了好久想說邏輯沒問題啊~
犯蠢了,謝謝你的熱心
這篇好像應該發在技術問答,不是技術文章