You are given an $m imes n$ grid of characters grid. A path in the grid starts at the top left cell $(0, 0)$ and ends at the bottom right cell $(m - 1, n - 1)$. At each step, you can only move either down to cell $(r + 1, c)$ or right to cell $(r, c + 1)$ from the current cell $(r, c)$.

The parentheses string corresponding to a path is formed by concatenating the characters of all cells visited along the path in the order they are traversed.

Return true if there is a path from $(0, 0)$ to $(m - 1, n - 1)$ that forms a valid parentheses string. Otherwise, return false.

A parentheses string is valid if:

• It is an empty string,

• It can be written as the concatenation of two valid parentheses strings, or

• It can be written as '(' followed by a valid parentheses string followed by ')'.

Constraints:

• m $=$ grid.length

• n $=$ grid[i].length

• $1 \leq$ m, n $\leq 100$

• grid[i][j] is either '(' or ')'

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.