单词搜索(中等题)

2020-09-14


给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。


示例:

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

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

采用回溯的思想，每匹配一个字母，在周围（上下左右）找一个接下来的字母，如果不匹配返回上层重新查找


public class FindWordInBoard {
    public static void main(String[] args) {

//        char board[][] = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
//        String word = "SEE";
//        char board[][]={{'a','a'}};
//        String word="a";
//        char board[][]={{'a','a','a','a'},
//                        {'a','a','a','a'},
//                        {'a','a','a','a'},
//                        {'a','a','a','a'},
//                        {'a','a','a','b'}};
//        String word="aaaaaaaaaaaaaaaaaaaa";

        char board[][]={{'A','B','C','E'},
                        {'S','F','E','S'},
                        {'A','D','E','E'}};
        String word="ABCESEEEFS";

        boolean flag = exist(board, word);
        System.out.println(flag);
    }

    public static boolean exist(char[][] board, String word) {

        int road[][] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        if(word.length()>board.length*board[0].length){//如果字符的长度大于棋盘中所有元素的数量，那么一定不匹配
            return false;
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if(word.length()==1){//如果单词只有一个字母，并且存在一个匹配，那么匹配
                        return true;
                    }
                    boolean[][] flags = new boolean[board.length][board[0].length];
                    flags[i][j]=true;//设置棋盘i,j位置已经遍历过
                    boolean flag = findPath(board, word, i, j, road, 1, flags);
                    if (flag) {//下层都匹配，本层也匹配，那么完全匹配
                        return true;
                    }

                }
            }
        }

        return false;
    }

    public static boolean findPath(char[][] board, String word, int i, int j, int[][] road, int cur, boolean[][] flags) {
        int max_i = board.length;
        int max_j = board[0].length;
        if(cur>=word.length()){//如果超出了单词的长度，直接终止
            return false;
        }
        for (int r = 0; r < 4; r++) {//向上下左右四个方向查找匹配的字母
            int x = i + road[r][0];
            int y = j + road[r][1];
            if (x < max_i && y < max_j && x >= 0 && y >= 0 && flags[x][y] == false) {//如果坐标有效并且没被占用

                if (board[x][y] == word.charAt(cur)) {//如果匹配
                    flags[x][y] = true;
                    if (cur == word.length() - 1) {//如果当前匹配已经是最后一个字母匹配，那么已经完全匹配字符串
                        return true;
                    }
                    boolean flag = findPath(board, word, x, y, road, cur + 1, flags);
                    if (flag) {
                        return true;
                    } else {
                        flags[x][y]=false;//如果当前的坐标没有匹配成功，清空已经占用的字母
                    }
                }
            }
        }
        return false;
    }
}

官方解题思路，貌似效率也不是特别高

class Solution {
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        if (board[i][j] != s.charAt(k)) {
            return false;
        } else if (k == s.length() - 1) {
            return true;
        }
        visited[i][j] = true;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if (!visited[newi][newj]) {
                    boolean flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}

评论区效率比较高的一种写法


class Solution {

    private char[][] mat;

    private int n, m;

    private int[] dx = new int[]{-1, 0, 1, 0};

    private int[] dy = new int[]{0, 1, 0, -1};

    private boolean[][] used;

    public boolean exist(char[][] board, String word) {
        n = board.length;
        m = board[0].length;
        mat = board;
        used = new boolean[n][m];
        char[] chars = word.toCharArray();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                boolean ans = dfs(chars, 0, i, j);
                if (ans) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[] word, int index, int i, int j) {
        if (index >= word.length) return true;
        if (!isOK(i, j) || used[i][j] || mat[i][j] != word[index]) return false;
        used[i][j] = true;
        boolean ans = false;
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            ans |= dfs(word, index + 1, x, y);
            if (ans) break;
        }
        used[i][j] = false;
        return ans;
    }

    private boolean isOK(int i, int j) {
        return i >= 0 && i < n && j >= 0 && j < m;
    }
}