[LeetCode] 79. 단어 검색 단어 검색

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent"cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word =  "ABCCED" , -> returns  true ,word =  "SEE" , -> returns  true ,word =  "ABCB" , -> returns  false .
2 차원 알파벳 보드 를 지정 하여 주어진 단 어 를 구성 하 는 격자 경로 가 있 는 지 판단 합 니 다.
해법: DFS, 전형 적 인 깊이 를 우선 적 으로 옮 겨 다 니 며 모든 경로 에 대해 깊이 있 게 옮 겨 다 니 며 옮 겨 다 니 는 과정 에서 나타 나 면:
1. 배열 이 경 계 를 넘는다.2. 이 점 은 이미 방문 했다.3. 이 점 의 문 자 는 워드 에 대응 하 는 index 문자 와 일치 하지 않 습 니 다.
이 경 로 를 가지치기 해 야 합 니 다:
Java:

public boolean exist(char[][] board, String word) {
    int m = board.length;
    int n = board[0].length;
 
    boolean result = false;
    for(int i=0; i=m || j>=n){
        return false;
    }
 
    if(board[i][j] == word.charAt(k)){
        char temp = board[i][j];
        board[i][j]='#';
        if(k==word.length()-1){
            return true;
        }else if(dfs(board, word, i-1, j, k+1)
        ||dfs(board, word, i+1, j, k+1)
        ||dfs(board, word, i, j-1, k+1)
        ||dfs(board, word, i, j+1, k+1)){
            return true;
        }
        board[i][j]=temp;
    }
 
    return false;
}　

Java:

class Solution {
    int[] dh = {0, 1, 0, -1};  
    int[] dw = {1, 0, -1, 0};
  
    public boolean exist(char[][] board, String word) {  
        boolean[][] isVisited = new boolean[board.length][board[0].length];  
        for (int i = 0; i < board.length; i++)  
            for (int j = 0; j < board[0].length; j++)  
                if (isThisWay(board, word, i, j, 0, isVisited)) return true;  
        return false;  
    }  
  
    public boolean isThisWay(char[][] board, String word, int row, int column, int index, boolean[][] isVisited) {  
        if (row < 0 || row >= board.length || column < 0 || column >= board[0].length  
            || isVisited[row][column] || board[row][column] != word.charAt(index))  
                return false;  //    
        if (++index == word.length()) return true;  //word          
        isVisited[row][column] = true;  
        for (int i = 0; i < 4; i++)  
            if (isThisWay(board, word, row + dh[i], column + dw[i], index, isVisited))  
                return true;  // board[row][column]        word    
        isVisited[row][column] = false;  //    ，            
        return false;  
    } 
}　　

Python:

class Solution:
    # @param board, a list of lists of 1 length string
    # @param word, a string
    # @return a boolean
    def exist(self, board, word):
        visited = [[False for j in xrange(len(board[0]))] for i in xrange(len(board))]
        
        for i in xrange(len(board)):
            for j in xrange(len(board[0])):
                if self.existRecu(board, word, 0, i, j, visited):
                    return True
        
        return False
    
    def existRecu(self, board, word, cur, i, j, visited):
        if cur == len(word):
            return True
        
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j] or board[i][j] != word[cur]:
            return False
        
        visited[i][j] = True
        result = self.existRecu(board, word, cur + 1, i + 1, j, visited) or\
                 self.existRecu(board, word, cur + 1, i - 1, j, visited) or\
                 self.existRecu(board, word, cur + 1, i, j + 1, visited) or\
                 self.existRecu(board, word, cur + 1, i, j - 1, visited)         
        visited[i][j] = False
        
        return result

C++:

class Solution {
public:
    bool exist(vector > &board, string word) {
        if (word.empty()) return true;
        if (board.empty() || board[0].empty()) return false;
        vector > visited(board.size(), vector(board[0].size(), false));
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (search(board, word, 0, i, j, visited)) return true;
            }
        }
        return false;
    }
    bool search(vector > &board, string word, int idx, int i, int j, vector > &visited) {
        if (idx == word.size()) return true;
        if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || visited[i][j] || board[i][j] != word[idx]) return false;
        visited[i][j] = true;
        bool res = search(board, word, idx + 1, i - 1, j, visited) 
                 || search(board, word, idx + 1, i + 1, j, visited)
                 || search(board, word, idx + 1, i, j - 1, visited)
                 || search(board, word, idx + 1, i, j + 1, visited);
        visited[i][j] = false;
        return res;
    }
};　

 
유사 한 제목:
[LeetCode] 212. 단어 검색 II 단어 검색 II
[LeetCode] 348. Design Tic - Tac - Toe 디자인 정자 기 게임
 
 
모든 LeetCode 질문 목록 제목 집계
　　
 
다음으로 전송:https://www.cnblogs.com/lightwindy/p/8587082.html