Java实现 LeetCode 212 单词搜索 II（二）

212. 单词搜索 II

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

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

示例:

输入:

words = ["oath","pea","eat","rain"] and board =

[

  ['o','a','a','n'],

  ['e','t','a','e'],

  ['i','h','k','r'],

  ['i','f','l','v']

]

输出: ["eat","oath"]

说明:

你可以假设所有输入都由小写字母 a-z 组成。

提示:

你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？

如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题：实现Trie（前缀树）。

PS：

首先构建一个字典树，然后在dfs的时候加入字典树，以某个字符串结尾的可以减少搜索次数

这里为什么不用开头用结尾呢， (●ˇ∀ˇ●)

结尾在这里就是我搜索完一个，我可以直接比较，如果没有的话，我再返回上一个，

class TrieNode {

    private static final int ALPHABET_SIZE = 26;

    TrieNode[] children = new TrieNode[ALPHABET_SIZE];

    // 判断这个前缀是不是某个字符串的结尾

    boolean isEndOfWord = false;

    TrieNode() {

        isEndOfWord = false;

        for (int i = 0; i < ALPHABET_SIZE; i++)

            children[i] = null;

    }

}

class Trie {

    public TrieNode root;

    /** Initialize your data structure here. */

    public Trie() {

        root = new TrieNode();

    }

    /** Inserts a word into the trie. */

    public void insert(String word) {

        TrieNode curNode = root;

        int index;

        for (int i = 0; i < word.length(); i++) {

            index = word.charAt(i) - 'a';

            if (curNode.children[index] == null) {

                curNode.children[index] = new TrieNode();

            }

            curNode = curNode.children[index];

        }

        curNode.isEndOfWord = true;

    }

}

class Solution {

    public List<String> findWords(char[][] board, String[] words) {

        List<String> result = new ArrayList<>();

        if (words == null || words.length == 0 || board == null || board.length == 0 || board[0].length == 0)

            return result;

        Trie trie = new Trie();

        for (String temp : words)

            trie.insert(temp);

        TrieNode root = trie.root;

        boolean[][] visited = new boolean[board.length][board[0].length];

        Set<String> tempResult = new HashSet<>();

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < board.length; i++) {

            for (int j = 0; j < board[0].length; j++) {

                if (root.children[board[i][j] - 'a'] != null ) {

                    dfs(board, visited, i, j, root.children[board[i][j] - 'a'], tempResult, sb);

                }

            }

        }

        // 需要把tempResult这个set拷贝到真正的result List中进行返回

        Iterator<String> iterator = tempResult.iterator();

        while (iterator.hasNext()) {

            result.add(iterator.next());

        }

        return result;

    }

    private void dfs(char[][] board, boolean[][] visited, int startIInBoard, int startJInBoard

            , TrieNode curNode, Set<String> resultSet, StringBuilder curStrBuilder) {

        curStrBuilder.append(board[startIInBoard][startJInBoard]);

        visited[startIInBoard][startJInBoard] = true;

        if (curNode.isEndOfWord) {

            resultSet.add(curStrBuilder.toString());

        }

        // 向上搜索, 如果上面的格子没有被搜索过的话

        if (startIInBoard > 0 && !visited[startIInBoard - 1][startJInBoard]

                && curNode.children[board[startIInBoard - 1][startJInBoard] - 'a'] != null) {

            dfs(board, visited,startIInBoard - 1, startJInBoard

                    , curNode.children[board[startIInBoard - 1][startJInBoard] - 'a'], resultSet, curStrBuilder);

        }

        // 向下搜索

        if (startIInBoard < board.length - 1 && !visited[startIInBoard + 1][startJInBoard]

                && curNode.children[board[startIInBoard + 1][startJInBoard] - 'a'] != null) {

            dfs(board, visited,startIInBoard + 1, startJInBoard

                    , curNode.children[board[startIInBoard + 1][startJInBoard] - 'a'], resultSet, curStrBuilder);

        }

        // 向左搜索

        if (startJInBoard > 0 && !visited[startIInBoard][startJInBoard - 1]

                && curNode.children[board[startIInBoard][startJInBoard - 1] - 'a'] != null) {

            dfs(board, visited, startIInBoard, startJInBoard - 1

                    , curNode.children[board[startIInBoard][startJInBoard - 1] - 'a'], resultSet, curStrBuilder);

        }

        // 向右搜索

        if (startJInBoard < board[0].length - 1 && !visited[startIInBoard][startJInBoard + 1]

                && curNode.children[board[startIInBoard][startJInBoard + 1] - 'a'] != null) {

            dfs(board, visited, startIInBoard, startJInBoard + 1

                    , curNode.children[board[startIInBoard][startJInBoard + 1] - 'a'], resultSet, curStrBuilder);

        }

        // 恢复现场

        curStrBuilder.setLength(curStrBuilder.length() - 1);

        visited[startIInBoard][startJInBoard] = false;

    }

}

巴特西

Java实现 LeetCode 212 单词搜索 II（二）

212. 单词搜索 II

最新文章

热门文章