日韩黄色影,91性视频,99热99官方网站,欧美另类巨大,黄色影片在线观看,免费一级黄色视频网站,日韩精品在线免费观看视频,依依成人大香蕉

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做 單詞搜索 II，我們先來看題面：

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

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

題意

給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)單詞（字符串）列表 words，找出所有同時(shí)在二維網(wǎng)格和字典中出現(xiàn)的單詞。

單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母在一個(gè)單詞中不允許被重復(fù)使用。

示例

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

輸出：["eat","oath"]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一個(gè)小寫英文字母
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] 由小寫英文字母組成
words 中的所有字符串互不相同

解題

方法：前綴樹+深度優(yōu)先搜索。

public class Solution {
    private TrieNode root = new TrieNode();
    private int[] ro = {-1, 1, 0, 0};
    private int[] co = {0, 0, -1, 1};
    private void find(char[][] board, boolean[][] visited, int row, int col, TrieNode node, Set<String> founded) {
        visited[row][col] = true;
        TrieNode current = node.nexts[board[row][col]-'a'];
        if (current.word != null) founded.add(current.word);
        for(int i=0; i<4; i++) {
            int nr = row + ro[i];
            int nc = col + co[i];
            if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[nr].length || visited[nr][nc]) continue;
            TrieNode next = current.nexts[board[nr][nc]-'a'];
            if (next != null) find(board, visited, nr, nc, current, founded);
        }
        visited[row][col] = false;
    }
    public List<String> findWords(char[][] board, String[] words) {
        Set<String> founded = new HashSet<>();
        for(int i=0; i<words.length; i++) {
            char[] wa = words[i].toCharArray();
            TrieNode node = root;
            for(int j=0; j<wa.length; j++) node = node.append(wa[j]);
            node.word = words[i];
        }
        boolean[][] visited = new boolean[board.length][board[0].length];
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[i].length; j++) {
                if (root.nexts[board[i][j]-'a'] != null) find(board, visited, i, j, root, founded);
            }
        }
        List<String> results = new ArrayList<>();
        results.addAll(founded);
        return results;
    }
}
class TrieNode {
    String word;
    TrieNode[] nexts = new TrieNode[26];
    TrieNode append(char ch) {
        if (nexts[ch-'a'] != null) return nexts[ch-'a'];
        nexts[ch-'a'] = new TrieNode();
        return nexts[ch-'a'];
    }
}