LeetCode #79 Word Search

Posted on | Post modified | In , , , , , ,

Problem

Given a 2D board and a word, find if the word exists in the grid.

The word can 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.

Example

1
2
3
4
5
6
7
8
9
10
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

What are the edge cases?

  • Some character of the word is not in the board
  • You can find the character in the board, but the total number of such caracter is more than the existence number in the board

Solution

Method: Backtracking

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Solution:
    def __init__(self):
        self.board = None
        self.result = False

    # def find_index(self, letter):
    #     ret = []
    #     for idx_i, row in enumerate(self.board):
    #         for idx_j, col in enumerate(row):
    #             if col == letter:
    #                 ret.append((idx_i, idx_j))
    #     return ret

    def construct_table(self):
        self.table = {}
        for idx_i, row in enumerate(self.board):
            for idx_j, letter in enumerate(row):
                if letter not in self.table:
                    self.table[letter] = [(idx_i, idx_j)]
                else:
                    self.table[letter].append((idx_i, idx_j))

    def is_neighbor(self, pt1, pt2):
        return (pt1[0] == pt2[0] and (pt1[1] == pt2[1] + 1 or pt1[1] == pt2[1] - 1)) or \
               (pt1[1] == pt2[1] and (pt1[0] == pt2[0] + 1 or pt1[0] == pt2[0] - 1))

    def construct_candidates(self, answer, kth, info):
        candidates = []

        if kth == 1:
            return self.table[info[0]][:]

        for candidate in self.table[info[kth - 1]]:
            if candidate in answer:
                continue
            if self.is_neighbor(answer[-1], candidate):
                candidates.append(candidate)

        return candidates

    def backtracking(self, answer, kth, info):
        if kth == len(info):
            self.result = True
        else:
            kth += 1
            candidates = self.construct_candidates(answer, kth, info)
            for candidate in candidates:
                answer.append(candidate)
                self.backtracking(answer, kth, info)
                answer.pop()

    def first_match(self, word):
        table = {}

        for letter in word:
            if letter not in table:
                table[letter] = 1
            else:
                table[letter] += 1
        
        for idx, key in enumerate(table):
            if key not in self.table:
                return False
            if table[key] > len(self.table[key]):
                return False
        
        return True

    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not word:
            return True

        self.board = board
        self.construct_table()

        if not self.first_match(word):
            return False
        
        self.backtracking([], 0, word)
        
        return self.result

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def exist(self, board, word):
    if not board:
        return False
    for i in xrange(len(board)):
        for j in xrange(len(board[0])):
            if self.dfs(board, i, j, word):
                return True
    return False

# check whether can find word, start at (i,j) position    
def dfs(self, board, i, j, word):
    if len(word) == 0: # all the characters are checked
        return True
    if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or word[0]!=board[i][j]:
        return False
    tmp = board[i][j]  # first character is found, check the remaining part
    board[i][j] = "#"  # avoid visit agian 
    # check whether can find "word" along one direction
    res = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) \
    or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:])
    board[i][j] = tmp
    return res