212. 单词搜索 II

题目描述

输入一个 m x n 的字母网格 board 和一个单词列表 words。返回 words 中所有能在网格里拼出来的单词，顺序任意。

拼一个单词时，从某个格子出发，每次走到上下左右相邻的格子，依次经过的字母要正好组成这个单词。在同一个单词里，每个格子最多用一次。

示例 1

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

解释："oath" 和 "eat" 都能沿相邻格子拼出，"pea" 和 "rain" 不能。

示例 2

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

解释：拼 "abcb" 需要重复使用写着 b 的格子，不允许。

数据范围

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 中的字符串两两不同。

解题思路

先把所有单词放进字典树（Trie），单词结尾节点用 $ 记下整个单词。然后从每个格子出发做回溯：当前字符不是 Trie 节点的孩子就立刻返回；否则走到孩子节点，若它有 $ 就记录单词并清空（避免重复），再把格子标成 # 向四个方向搜索，最后恢复格子。一次搜索同时匹配所有共享前缀的单词。

为什么正确

dfs(r, c, node) 时，当前路径上的字符恰好是从 Trie 根走到 node 的前缀，路径上的格子都被标成了 #。

复杂度分析

最坏 O(m·n·4·3^(L-1))，L 为最长单词长度；Trie 空间为所有单词长度之和。

易错点

找到单词后要清空节点的 $，否则同一个单词从不同起点被找到多次会重复加入答案；回溯返回前一定要恢复 board[r][c]。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = {}
        for w in words:
            node = root
            for ch in w:
                node = node.setdefault(ch, {})
            node['$'] = w
        m, n = len(board), len(board[0])
        res = []

        def dfs(r, c, node):
            ch = board[r][c]
            if ch not in node:
                return
            nxt = node[ch]
            if nxt.get('$'):
                res.append(nxt['$'])
                nxt['$'] = None
            board[r][c] = '#'
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    dfs(nr, nc, nxt)
            board[r][c] = ch

        for r in range(m):
            for c in range(n):
                dfs(r, c, root)
        return res

class Solution {
    static class Node {
        Node[] next = new Node[26];
        String word;
    }
    char[][] board;
    List<String> res = new ArrayList<>();
    int m, n;

    public List<String> findWords(char[][] board, String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node node = root;
            for (char ch : w.toCharArray()) {
                if (node.next[ch - 'a'] == null) node.next[ch - 'a'] = new Node();
                node = node.next[ch - 'a'];
            }
            node.word = w;
        }
        this.board = board;
        m = board.length;
        n = board[0].length;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                dfs(r, c, root);
            }
        }
        return res;
    }

    void dfs(int r, int c, Node node) {
        char ch = board[r][c];
        if (ch == '#' || node.next[ch - 'a'] == null) {
            return;
        }
        Node nxt = node.next[ch - 'a'];
        if (nxt.word != null) {
            res.add(nxt.word);
            nxt.word = null;
        }
        board[r][c] = '#';
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                dfs(nr, nc, nxt);
            }
        }
        board[r][c] = ch;
    }
}

class Solution {
    struct Node {
        Node* next[27] = {};
        string word;
    };
    vector<vector<char>>* bp;
    vector<string> res;
    int m, n;

    void dfs(int r, int c, Node* node) {
        auto& board = *bp;
        char ch = board[r][c];
        if (ch == '#' || !node->next[ch - 'a']) {
            return;
        }
        Node* nxt = node->next[ch - 'a'];
        if (!nxt->word.empty()) {
            res.push_back(nxt->word);
            nxt->word = "";
        }
        board[r][c] = '#';
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                dfs(nr, nc, nxt);
            }
        }
        board[r][c] = ch;
    }

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Node* root = new Node();
        for (auto& w : words) {
            Node* node = root;
            for (char ch : w) {
                if (!node->next[ch - 'a']) node->next[ch - 'a'] = new Node();
                node = node->next[ch - 'a'];
            }
            node->word = w;
        }
        m = board.size();
        n = board[0].size();
        bp = &board;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                dfs(r, c, root);
            }
        }
        return res;
    }
};

type trieNode212 struct {
	next [26]*trieNode212
	word string
}

func findWords(board [][]byte, words []string) []string {
	root := &trieNode212{}
	for _, w := range words {
		node := root
		for i := 0; i < len(w); i++ {
			ch := w[i] - 'a'
			if node.next[ch] == nil {
				node.next[ch] = &trieNode212{}
			}
			node = node.next[ch]
		}
		node.word = w
	}
	m, n := len(board), len(board[0])
	res := []string{}
	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	var dfs func(r, c int, node *trieNode212)
	dfs = func(r, c int, node *trieNode212) {
		ch := board[r][c]
		if ch == '#' || node.next[ch-'a'] == nil {
			return
		}
		nxt := node.next[ch-'a']
		if nxt.word != "" {
			res = append(res, nxt.word)
			nxt.word = ""
		}
		board[r][c] = '#'
		for _, d := range dirs {
			nr, nc := r+d[0], c+d[1]
			if nr >= 0 && nr < m && nc >= 0 && nc < n {
				dfs(nr, nc, nxt)
			}
		}
		board[r][c] = ch
	}
	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			dfs(r, c, root)
		}
	}
	return res
}

var findWords = function(board, words) {
    const root = {};
    for (const w of words) {
        let node = root;
        for (const ch of w) {
            node = node[ch] || (node[ch] = {});
        }
        node.$ = w;
    }
    const m = board.length, n = board[0].length;
    const res = [];
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    const dfs = (r, c, node) => {
        const ch = board[r][c];
        if (ch === '#' || !node[ch]) {
            return;
        }
        const nxt = node[ch];
        if (nxt.$) {
            res.push(nxt.$);
            nxt.$ = null;
        }
        board[r][c] = '#';
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                dfs(nr, nc, nxt);
            }
        }
        board[r][c] = ch;
    };
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            dfs(r, c, root);
        }
    }
    return res;
};

function findWords(board: string[][], words: string[]): string[] {
    const root: any = {};
    for (const w of words) {
        let node = root;
        for (const ch of w) {
            node = node[ch] || (node[ch] = {});
        }
        node.$ = w;
    }
    const m = board.length, n = board[0].length;
    const res: string[] = [];
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    const dfs = (r: number, c: number, node: any): void => {
        const ch = board[r][c];
        if (ch === '#' || !node[ch]) {
            return;
        }
        const nxt = node[ch];
        if (nxt.$) {
            res.push(nxt.$);
            nxt.$ = null;
        }
        board[r][c] = '#';
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                dfs(nr, nc, nxt);
            }
        }
        board[r][c] = ch;
    };
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            dfs(r, c, root);
        }
    }
    return res;
}

载入编辑器，自己跑一遍 →

回溯专题的其他题目

查看回溯全部题目 →