Test Whether a Right-and-Down Grid Path Forms Balanced Parentheses
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Choose a path from the upper-left to the bottom-right cell of `grid`, moving only right or down. Read every visited parenthesis, including both endpoints. Return whether at least one resulting nonempty string is balanced in the usual nesting order.
```cpp
class Solution {
public:
bool hasValidPath(vector<vector<char>>& grid);
};
```
### Examples
**Example 1:**
```text
Input: grid = [["(",")"]]
Output: true
Explanation: The only path spells "()", a balanced parenthesis string.
```
**Example 2:**
```text
Input: grid = [["(","("],[")",")"]]
Output: false
Explanation: Every path contains three characters, so it cannot contain equal counts of opening and closing parentheses.
```
### Constraints
- `1 <= m, n <= 100`.
- grid is rectangular and each cell is ( or ).
### Clarifying Questions
- Are the endpoint characters included? Yes, every visited cell contributes one character.
- What makes the string balanced? Each closing parenthesis must match an earlier unmatched opening parenthesis, with none left unmatched at the end.
- Can a path move left or up? No. Every path visits exactly `m + n - 1` cells.
- Is one valid path sufficient? Yes; return a boolean, not the path.
```hint Check the boundary
Check the length and endpoint characters before considering different routes.
```
Overview: Decide whether a right-and-down path through a parenthesis grid spells a balanced string, including both endpoints in the path.
