Problem

Given a 2D matrix of characters and a target word, write a function that returns whether the word can be found in the matrix by going left-to-right, or up-to-down.

Examples

Example 1

1
2
3

Input: matrix = [['F', 'A', 'C', 'I'], ['O', 'B', 'Q', 'P'], ['A', 'N', 'O', 'B'], ['M', 'A', 'S', 'S']], word = "FOAM"
Output: true
Explanation: The word "FOAM" can be found in the leftmost column of the given matrix.

Example 2

1
2
3

Input: matrix = [['F', 'A', 'C', 'I'], ['O', 'B', 'Q', 'P'], ['A', 'N', 'O', 'B'], ['M', 'A', 'S', 'S']], word = "MASS"
Output: true
Explanation: The word "MASS" can be found in the last row of the given matrix.

Solution

Method 1 - Iteration

To find the target word in the matrix, we need to check each row and column to see if the word can be found either horizontally or vertically starting from each position. This involves comparing the target word with potential substrings within the matrix.

Approach

  1. Horizontal Search: Iterate through each row of the matrix and check if the target word exists as a substring in that row.
  2. Vertical Search: Iterate through each column of the matrix, construct the column as a string, and check if the target word exists as a substring in that column.
  3. If either condition is satisfied, return true.

Code

 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

class Solution {
    public boolean findWord(char[][] matrix, String word) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int len = word.length();

        // Check each row
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j <= cols - len; j++) {
                if (checkRow(matrix, word, i, j)) {
                    return true;
                }
            }
        }

        // Check each column
        for (int j = 0; j < cols; j++) {
            for (int i = 0; i <= rows - len; i++) {
                if (checkColumn(matrix, word, i, j)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean checkRow(char[][] matrix, String word, int row, int col) {
        for (int k = 0; k < word.length(); k++) {
            if (matrix[row][col + k] != word.charAt(k)) {
                return false;
            }
        }
        return true;
    }

    private boolean checkColumn(char[][] matrix, String word, int row, int col) {
        for (int k = 0; k < word.length(); k++) {
            if (matrix[row + k][col] != word.charAt(k)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] matrix = {
            {'F', 'A', 'C', 'I'},
            {'O', 'B', 'Q', 'P'},
            {'A', 'N', 'O', 'B'},
            {'M', 'A', 'S', 'S'}
        };
        System.out.println(sol.findWord(matrix, "FOAM")); // Output: true
        System.out.println(sol.findWord(matrix, "MASS")); // Output: true
        System.out.println(sol.findWord(matrix, "FACE")); // Output: false
    }
}
 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

class Solution:
    def findWord(self, matrix: List[List[str]], word: str) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])
        len_word = len(word)

        # Check each row
        for i in range(rows):
            for j in range(cols - len_word + 1):
                if self.checkRow(matrix, word, i, j):
                    return True

        # Check each column
        for j in range(cols):
            for i in range(rows - len_word + 1):
                if self.checkColumn(matrix, word, i, j):
                    return True

        return False

    def checkRow(self, matrix: List[List[str]], word: str, row: int, col: int) -> bool:
        for k in range(len(word)):
            if matrix[row][col + k] != word[k]:
                return False
        return True

    def checkColumn(self, matrix: List[List[str]], word: str, row: int, col: int) -> bool:
        for k in range(len(word)):
            if matrix[row + k][col] != word[k]:
                return False
        return True

if __name__ == "__main__":
    sol = Solution()
    matrix = [
        ['F', 'A', 'C', 'I'],
        ['O', 'B', 'Q', 'P'],
        ['A', 'N', 'O', 'B'],
        ['M', 'A', 'S', 'S']
    ]
    print(sol.findWord(matrix, "FOAM")) # Output: True
    print(sol.findWord(matrix, "MASS")) # Output: True
    print(sol.findWord(matrix, "FACE")) # Output: False

Complexity

  • ⏰ Time complexity: O(m * n * l), where m is the number of rows, n is the number of columns, and l is the length of the target word. This accounts for checking each potential starting position in the matrix.
  • 🧺 Space complexity: O(1) for extra space if we ignore the space needed for storing the matrix and the input word.