iT邦幫忙

0

Leetcode 79 Word Search (JavaScript) 的問題

各位邦友好,敝人想問一下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起
不知這裡有沒有高手願意提點,謝謝!


1 則留言

0

最後一個 word.substr(1) 沒包到 dfs。 ((看了好久想說邏輯沒問題啊~

ffaanngg iT邦新手 5 級 ‧ 2020-10-29 03:08:31 檢舉

犯蠢了,謝謝你的熱心

ffaanngg iT邦新手 5 級 ‧ 2020-10-29 03:26:06 檢舉

這篇好像應該發在技術問答,不是技術文章

我要留言

立即登入留言