LeetCode #212 Word Search II
Problem
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:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]Output: ["eat","oath"]
Note:
You may assume that all inputs are consist of lowercase letters a-z.
Solution
We will use a trie to save all words and perform DFS start from each element. Once there is a node in trie which has no corresponding letter, terminate DFS immediately. Thus the search domain will be pruned.
Complexity
It’s too difficulty for me to estimate time complexity of this approach. But it’s clear that the visited matrix uses O(mn) extra space, where m and n denote to number of rows and columns of the given board. And the trie needs O(k) extra space, where k denotes to total counts of letters in the given words list. Therefore, space complexity will be O(mn + k).
