用java解决单词搜索问题

Question

单词搜索
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

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

示例 1：

输入：

board = [
["o","a","a","n"],
["e","t","a","e"],
["i","h","k","r"],
["i","f","l","v"]
], 
words = ["oath","pea","eat","rain"]

输出：["eat","oath"]
示例 2：

输入：board = [
["a","b"],
["c","d"]
],
words = ["abcb"]
输出：[]
提示：

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 10^4
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同

Answer 1

class Solution {
    static int[][] d = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    static Map<String, Boolean> notExistWords = new HashMap<>();
    public List<String> findWords(char[][] board, String[] words) {
        List<String> ans = new ArrayList<>();
        Arrays.sort(words);
        notExistWords.clear();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (i > 0 && word.equals(words[i - 1]))
                continue;
            boolean notExistFlag = false;
            for (int j = 1; j < word.length(); j++) {
                if (notExistWords.containsKey(word.substring(0, j + 1))) {
                    notExistFlag = true;
                    break;
                }
            }
            if (notExistFlag)
                continue;
            if (exist(board, word)) {
                ans.add(word);
            } else {
                notExistWords.put(word, false);
            }
        }
        return ans;
    }
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        if (m == 0)
            return false;
        int n = board[0].length;
        if (n == 0)
            return false;
        if (word.equals(""))
            return true;
        boolean[][] f = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (word.charAt(0) == board[i][j]) {
                    f[i][j] = true;
                    boolean flag = dfs(i, j, 1, board, word, m, n, f);
                    if (flag)
                        return true;
                    f[i][j] = false;
                }
            }
        }
        return false;
    }
    private boolean dfs(int i, int j, int k, char[][] board, String word, int m, int n, boolean[][] f) {
        if (k == word.length()) {
            return true;
        }
        for (int l = 0; l < 4; l++) {
            if (i + d[l][0] < m && j + d[l][1] < n && i + d[l][0] >= 0 && j + d[l][1] >= 0
                    && board[i + d[l][0]][j + d[l][1]] == word.charAt(k) && !f[i + d[l][0]][j + d[l][1]]) {
                f[i + d[l][0]][j + d[l][1]] = true;
                boolean flag = dfs(i + d[l][0], j + d[l][1], k + 1, board, word, m, n, f);
                if (flag)
                    return true;
                f[i + d[l][0]][j + d[l][1]] = false;
            }
        }
        return false;
    }
}