各位邦友好,敝人想问一下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起
不知这里有没有高手愿意提点,谢谢!