Leetcode79. Word Search (w. kotlin)

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:

 

val board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
val word = "SEE"

Output: true

 

Approach 

해당 문제는 Backtracking 을 사용하여 상하좌우 의 문자열을 이어 나가면서 기대하는 Word 와 일치 하는지 에 대한 결과를 구하는 문제입니다.

 

• word = "SEE" 중 S 가 위치한 (row, col) 값을 찾습니다. 
• (1, 0) 에 위치한 S 의 상하좌우 를 DFS 로 탐색합니다. 방문한 곳은 board 에 "*" 로 마킹합니다. 
• LEFT (index 를 벗어남) , RIGHT(F 유효하지않음), UP(A 유효하지 않음), DOWN(A 유효하지 않음) 상하좌우 모두 유효하지 않기 때문에 넘어갑니다.
• "*" 로 마킹 한 곳은 다시 문자열을 채워줍니다.
• (1, 3) 에 위치한 S 를 상하좌우 를 DFS 로 탐색합니다. DOWN 에 위치한 (E) 가 유효 하고 E 로 DFS 탐색을 했을시 LEFT 가 유효하여 true 가 retrun 됩니다.

 

fun exist(board: Array<CharArray>, word: String): Boolean {
    if (board.isEmpty()) return false
    if (word.isBlank()) return true

    val checker = Array(board.size) { BooleanArray(board.first().size) }
    for (i in board.indices) {
        for (j in board[i].indices) {
            if (helper(board, checker, word, i, j, 0)) {
                return true
            }
        }
    }
    return false
}

fun helper(
    board: Array<CharArray>,
    checker: Array<BooleanArray>,
    word: String,
    row: Int,
    col: Int,
    start: Int
): Boolean {
    if (start == word.length) return true
    if (!isValid(row, col, board) || board[row][col] != word[start]) return false

    board[row][col] = '*'
    val result = helper(board, checker, word, row + 1, col, start + 1) ||
            helper(board, checker, word, row - 1, col, start + 1) ||
            helper(board, checker, word, row, col + 1, start + 1) ||
            helper(board, checker, word, row, col - 1, start + 1)
    board[row][col] = word[start]
    return result
}

fun isValid(row: Int, col: Int, board: Array<CharArray>): Boolean {
    return row in (board.indices) && col in (board.first().indices)
}

fun main() {
    val board = arrayOf(
        charArrayOf('A', 'B', 'C', 'E'),
        charArrayOf('S', 'F', 'C', 'S'),
        charArrayOf('A', 'D', 'E', 'E'),
    )
    val word = "ABCCED"
    exist(board, word).also { println(it) }
}