欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

79. Word Search

程序员文章站 2022-07-14 17:31:03
...

Description

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.

Example:

board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]

Given word = “ABCCED”, return true.
Given word = “SEE”, return true.
Given word = “ABCB”, return false.
Problem URL


Solution

给一个字符的二维数组,搜索数组中是否存在给定的单词。

We could simply run a dfs to solve this problem. If word is with length 0, return true; If board is empty, return false. Then iteratively start dfs in each position.

In dfs, if out of bound or visited or word is different, retrun false, if match, return true. Set visited to true and count ++. Then recursively call dfs in four direction, remember reset visited to false for backtracking.

Code

class Solution {
    private int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 
    public boolean exist(char[][] board, String word) {
        if (word.length() == 0){
            return true;
        }
        if (board.length == 0 || board[0].length == 0){
            return false;
        }
        boolean[][] visited = 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 (dfs(board, word, i, j , 0, visited)){
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int i, int j, int count, boolean[][] visited){
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(count)){
            return false;
        }
        if (count == word.length() - 1){
            return true;
        }
        visited[i][j] = true;
        count++;
        for (int[] dir : dirs){
            int x = i + dir[0];
            int y = j + dir[1];
            if (dfs(board, word, x, y, count, visited)){
                return true;
            }
        }
        visited[i][j] = false;
        return false;
    }
}

Time Complexity: O()
Space Complexity: O()


Review

上一篇: 79. Word Search

下一篇: 79. Word Search