[leetcode #79] Word Search

Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

・ m == board.length
・ n = board[i].length
・ 1 <= m, n <= 6
・ 1 <= word.length <= 15
・ board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Idea

2d-array에서 path를 찾는 문제는 backtracking을 사용해서 푸는 경우가 많다. 이 문제 또한 예외는 아닌데, 막다른 길에 도달하면 backtracking을 통해 이미 확인한 path를 다시 찾지 않도록 해야 한다.

우선 주어진 2d array에서 시작점을 찾아야 한다. 시작점은 word의 첫 번째 문자이므로, array를 탐색하다가 word의 첫 번째 문자가 나올 경우 재귀함수를 호출하여 path 찾는 것을 시작한다. 이럴 때 이미 지나온 cell을 재활용하면 안 되므로 array 크기와 똑같은 크기의 boolean array(= visited)를 활용한다.

재귀함수에 진입할 때 visited flag array를 true로 설정한다. 재귀함수가 true를 리턴하는 경우는 word의 index가 마지막인 경우다. 재귀함수에서는 이미 방문한 cell이 아니고 word의 다음 문자가 인접한 cell에 있을 때 해당 cell의 index를 재귀함수의 인자로 하여 재호출한다. 인접한 cell을 확인하고 word를 만들지 못 하는 경우 false를 리턴하며, backtracking할 때 visited flag array도 false로 만들어준다.

모든 cell을 전부 방문한 뒤 word를 만드는 것이 불가능하다는 것이 확인되면 false를 리턴하고 word가 만들어지면 곧바로 true를 리턴한다.

Solution

class Solution {
    boolean[][] visited;
    int m;
    int n;

    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];

        for (int i=0; i < m; i++) {
            for (int j=0; j < n; j++) {
                if (board[i][j] == word.charAt(0) && findWay(board, word, i, j, 0))
                    return true;
            }
        }

        return false;
    }

    private boolean findWay(char[][] board, String word, int i, int j, int wordIndex) {
        visited[i][j] = true;
        if (wordIndex == word.length()-1)
            return true;

        boolean found = false;
        if (i-1 >= 0 && !visited[i-1][j] && board[i-1][j] == word.charAt(wordIndex+1))
            found = findWay(board, word, i-1, j, wordIndex+1);
        if (!found && j-1 >= 0 && !visited[i][j-1] && board[i][j-1] == word.charAt(wordIndex+1))
            found = findWay(board, word, i, j-1, wordIndex+1);
        if (!found && i+1 < m && !visited[i+1][j] && board[i+1][j] == word.charAt(wordIndex+1))
            found = findWay(board, word, i+1, j, wordIndex+1);
        if (!found && j+1 < n && !visited[i][j+1] && board[i][j+1] == word.charAt(wordIndex+1))
            found = findWay(board, word, i, j+1, wordIndex+1);

        visited[i][j] = false;
        return found;
    }
}

기대하지 않았는데 생각보다 너무나 좋은 결과가 나왔다!

Reference

https://leetcode.com/problems/word-search/