212. Word Search II (Hard)

https://leetcode.com/problems/word-search-ii/

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must 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 in a word.

 

Example:

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

Output: ["eat","oath"]

 

Note:

  1. All inputs are consist of lowercase letters a-z.
  2. The values of words are distinct.

Solutions

class Solution {
    private final int[] R = new int[]{0, 0, 1, -1};
    private final int[] C = new int[]{1, -1, 0, 0};

    private boolean[][] visited;

    private Set<String> ansSet = new HashSet<>();

    private Trie trie = new Trie();

    private Set<String> dict = new HashSet<>();

    public List<String> findWords(char[][] board, String[] words) {
        for (String w : words) {
            trie.insert(w);

            dict.add(w);
        }

        int row = board.length;
        int col = board[0].length;

        visited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                dfs(i, j, board, trie, board[i][j] + "");
            }
        }

        return new ArrayList<>(ansSet);
    }

    private void dfs(int r, int c, char[][] board, Trie trie, String s) {
        int row = board.length;
        int col = board[0].length;

        char newChar = board[r][c];
        Trie subTrie = trie.next(newChar);

        // optimization measure, means no words start with this subTrie,
        // roll back to prune this branch
        if (subTrie == null) {
            return;
        }

        visited[r][c] = true;

        // String s is in the candidate list for searching
        // But not return here since some other words may be prefixed with s
        if (dict.contains(s)) {
            ansSet.add(s);
        }

        for (int i = 0; i < 4; i++) {
            int newR = r + R[i];
            int newC = c + C[i];

            if (newR < 0 || newC < 0 || newR >= row || newC >= col) {
                continue;
            }

            if (!visited[newR][newC]) {
                dfs(newR, newC, board, subTrie, s + board[newR][newC]);
            }
        }

        visited[r][c] = false;
    }

    // IMPORTANT, recite the structure of Trie

    private class Trie {
        private Map<Character, Trie> map = new HashMap<>();

        public void insert(String word) {
            if (word == null) {
                return;
            }

            add(0, word);
        }

        private void add(int i, String word) {
            if (i >= word.length()) {
                map.put(null, new Trie()); //use null to indicate end of string
                return;
            }

            char c = word.charAt(i);
            Trie subTrie = map.get(c);
            if (subTrie == null) {
                subTrie = new Trie();
                map.put(c, subTrie);
            }

            subTrie.add(i + 1, word);
        }

        public Trie next(char c) {
            return this.map.get(c);
        }
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""