November 30, 2016 by oneOokay
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.
Given words =
["oath","pea","eat","rain"] and board =
[ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ]
You may assume that all inputs are consist of lowercase letters
DFS + Trie
Trie time complexity:
The complexity of creating a trie is
W is the number of words, and
L is an average length of the word: you need to perform
L lookups on the average for each of the
Wwords in the set.
Same goes for looking up words later: you perform
L steps for each of the
Hash insertions and lookups have the same complexity: for each word you need to check equality, which takes
O(L), for the overall complexity of