URL

Word Search - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202404/word_search/main.fsx

let exist (board: char[,]) (word: string) : bool =
    let rows, cols = Array2D.length1 board, Array2D.length2 board
    let steps = [ (-1, 0); (0, -1); (1, 0); (0, 1) ]
    let cs = Seq.toList word

    let rec search row col cs visited =
        match cs with
        | [] -> true
        | h :: [] -> h = board.[row, col]
        | h :: t ->
            if h = board.[row, col] then
                let nexts =
                    steps
                    |> List.map (fun (i, j) -> row + i, col + j)
                    |> List.filter (fun (i, j) -> i >= 0 && i < rows && j >= 0 && j < cols)
                    |> List.filter (fun (i, j) -> not <| Set.contains (i, j) visited)

                nexts
                |> List.fold (fun ok (i, j) -> if ok then true else search i j t (Set.add (i, j) visited)) false
            else
                false

    let rec exist' row col =
        if row >= rows then
            false
        elif col >= cols then
            exist' (row + 1) 0
        else if search row col cs (Set.empty |> Set.add (row, col)) then
            true
        else
            exist' row (col + 1)

    exist' 0 0