212. Word Search II

Published on March 30, 2023

Problem

Given a board and a set of words, each position is a character select the consecutive characters to form the word, consecutive means the start of a character up, down, left and right position, but can not be repeatedly moved. Find which words in the words exist on the board.

Algorithm

This topic is also a search for words, so consider using trie.

The overall idea is that we store the words in words into a trie, traverse each character for the beginning, dfs, to see if there is a word that begins with him ** exists in **trie (search to each position to see if isWord.) Because this word needs to be stored in the result set here, directly change the position of isWord to a string variable, save to This position can be composed of the word.

Here the use of backtracking thinking. When traversing this position, the character in this position will be set to #, and then directly skipped when encountered.

Code

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>().
        Trie trie = new Trie().
        for (String word : words) {
            trie.addWord(word).
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, res, trie.root).
            }
        }
        
        return res.
    }
    
    private void dfs(char[][] board, int i, int j, List<String> res, TrieNode curNode) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0) {
            return.
        }
        char c = board[i][j].
        if (c == '#' || curNode.children[c-'a'] == null) {
            return.
        }
        curNode = curNode.children[c-'a'].
        if (curNode.word ! = null) {
            res.add(curNode.word).
            curNode.word = null; // set as null to avoid repeat word added to res.
        }
        
        board[i][j] = '#'.
        dfs(board, i+1, j, res, curNode).
        dfs(board, i-1, j, res, curNode).
        dfs(board, i, j+1, res, curNode).
        dfs(board, i, j-1, res, curNode).
        board[i][j] = c.
        
        
    }
    
    class TrieNode {
        String word.
        TrieNode[] children.
        
        public TrieNode() {
            children = new TrieNode[26].
        }
    }
    
    class Trie {
        TrieNode root.
        
        public Trie() {
            root = new TrieNode().
        }
        
        public void addWord(String word) {
            TrieNode curNode = root.
            for (Character ch : word.toCharArray()) {
                if (curNode.children[ch-'a'] == null) {
                    curNode.children[ch-'a'] = new TrieNode().
                }
                curNode = curNode.children[ch-'a'].
            }
            curNode.word = word.
        }
    }
}

问题

给一个board和一组单词words，每一个位置都是一个字符选择连续的字符组成单词，连续是指一个字符的开始上下左右位置，但是不能反复移动。求哪些words中的单词存在于board上。

算法

这个题目也是搜索word，可以考虑使用trie。

整体思路是我们将words中的单词存到一个trie中，遍历每一个字符为开头，dfs，看是否有以他开头的单词存在于trie（搜索到每一个位置，看是否isWord。）因为这里需要将这个word存进去结果集，直接将isWord的位置改为一个字符串变量，保存到这个位置可以组成的word。

这里利用到了回溯的思维。在遍历这个位置的时候将这个位置的字符置为#,后续遇到的时候直接跳过。

代码

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        Trie trie = new Trie();
        for (String word : words) {
            trie.addWord(word);
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, res, trie.root);
            }
        }
        
        return res;
    }
    
    private void dfs(char[][] board, int i, int j, List<String> res, TrieNode curNode) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0) {
            return;
        }
        char c = board[i][j];
        if (c == '#' || curNode.children[c-'a'] == null) {
            return;
        }
        curNode = curNode.children[c-'a'];
        if (curNode.word != null) {
            res.add(curNode.word);
            curNode.word = null; // set as null to avoid repeat word added to res;
        }
        
        board[i][j] = '#';
        dfs(board, i+1, j, res, curNode);
        dfs(board, i-1, j, res, curNode);
        dfs(board, i, j+1, res, curNode);
        dfs(board, i, j-1, res, curNode);
        board[i][j] = c;
        
        
    }
    
    class TrieNode {
        String word;
        TrieNode[] children;
        
        public TrieNode() {
            children = new TrieNode[26];
        }
    }
    
    class Trie {
        TrieNode root;
        
        public Trie() {
            root = new TrieNode();
        }
        
        public void addWord(String word) {
            TrieNode curNode = root;
            for (Character ch : word.toCharArray()) {
                if (curNode.children[ch-'a'] == null) {
                    curNode.children[ch-'a'] = new TrieNode();
                }
                curNode = curNode.children[ch-'a'];
            }
            curNode.word = word;
        }
    }
}