Solution: Word Search II

Let's solve the Word Search II problem using the Trie pattern.

We'll cover the following

Statement
Solution
- Time complexity
- Space complexity

Statement#

You are given a list of strings that you need to find in a 2D grid of letters such that the string can be constructed from letters in sequentially adjacent cells. The cells are considered sequentially adjacent when they are neighbors to each other either horizontally or vertically. The solution should return a list containing the strings from the input list that were found in the grid.

Constraints:

$1 \leq$ rows, columns $\leq 12$
$1 \leq$ words.length $\leq 3 \times {10^3}$
$1 \leq$ words[i].length $\leq 10$
grid[i][j] is an uppercase English letter.
words[i] consists of uppercase English letters.
All the strings are unique.

Note: The order of the strings in the output does not matter.

Solution#

By using backtracking, we can explore different paths in the grid to search the string. We can backtrack and explore another path if a character is not a part of the search string. However, backtracking alone is an inefficient way to solve the problem, since several paths have to be explored to search for the input string.

By using the trie data structure, we can reduce this exploration or search space in a way that results in a decrease in the time complexity:

First, we’ll construct the Trie using all the strings in the list. This will be used to match prefixes.
Next, we’ll loop over all the cells in the grid and check if any string from the list starts from the letter that matches the letter of the cell.
Once an letter is matched, we use depth-first-search recursively to explore all four possible neighboring directions.
If all the letters of the string are found in the grid. This string is stored in the output result array.
We continue the steps of all our input strings.

1 of 50

2 of 50

3 of 50

4 of 50

5 of 50

6 of 50

7 of 50

8 of 50

9 of 50

10 of 50

11 of 50

12 of 50

13 of 50

14 of 50

15 of 50

16 of 50

17 of 50

18 of 50

19 of 50

20 of 50

21 of 50

22 of 50

23 of 50

24 of 50

25 of 50

26 of 50

27 of 50

28 of 50

29 of 50

30 of 50

31 of 50

32 of 50

33 of 50

34 of 50

35 of 50

36 of 50

37 of 50

38 of 50

39 of 50

40 of 50

41 of 50

42 of 50

43 of 50

44 of 50

45 of 50

46 of 50

47 of 50

48 of 50

49 of 50

50 of 50

main.py

trie.py

trie_node.py

from trie import Trie
def print_grid(grid):
    for i in grid:
        output = '   '.join(i)
        print("\t", output)
def find_strings(grid, words):
    trie_for_words = Trie()
    result = []
    for word in words:
        trie_for_words.insert(word)
    for j in range(len(grid)):
        for i in range(len(grid[0])):
            dfs(trie_for_words, trie_for_words.root, grid, j, i, result)       
    return result
def dfs(words_trie, node, grid, row, col, result, word=''):
    if node.is_string:
        result.append(word)
        node.is_string = False
        words_trie.remove_characters(word)
    
    if 0 <= row < len(grid) and 0 <= col < len(grid[0]):
        char = grid[row][col]
        child = node.children.get(char)
        if child is not None:
            word += char
            grid[row][col] = None
            for row_offset, col_offset in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                dfs(words_trie, child, grid, row + row_offset, col + col_offset, result, word)

Enter to Rename, Shift+Enter to Preview

Word Search II

Time complexity#

The time complexity will be $O(n*3^l)$ , where $n$ is equal to rows $*$ columns, and $l$ is the length of the longest string in the list. The factor $3^l$ means that, in the dfs() function, we have four directions to explore initially, but only three choices remain in each cell because one has already been explored. In the worst case, none of the strings will have the same prefix, so we cannot skip any string from the list.

Space complexity#

In the worst case, none of the strings will have the same prefix, so the space used by the trie data structure will be $O(m)$ , where $m$ is the total count of all the characters in all the strings present in the input list.

If there is a string of length equal to the length of the grid and the elements on the grid are arranged in such a way that the string can be traced, then the space acquired on the stack to store the recursive calls of dfs() function would be the size of the grid, which is $O(n)$ .

Hence, the overall space complexity of the solution will be $O(m+n)$ .

Word Search II

Custom Data Structures: Introduction