n be the grid dimensions. The path length is m + n - 1.

If the path length is odd, return false (cannot form a valid parentheses string).

Use a DP table where dp[i][j] is a set of possible balances at cell (i, j).

Initialize dp[0][0] with 1 if grid[0][0] == '(', else -1 (invalid if negative).

For each cell, propagate possible balances from the top and left neighbors, updating the balance according to the current cell's value. Only keep balances >= 0.

At the end, check if a balance of 0 is possible at the bottom-right cell.

Edge cases:

Path length is odd: impossible.
More ')' than '(' at any point: impossible.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    bool hasValidPath(vector<vector<char>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n        if ((m + n - 1) % 2) return false;\n        vector<vector<unordered_set<int>>> dp(m, vector<unordered_set<int>>(n));\n        dp[0][0].insert(grid[0][0] == '(' ? 1 : -1);\n        for (int i = 0; i < m; ++i) {\n            for (int j = 0; j < n; ++j) {\n                for (int d : {0, 1}) {\n                    int ni = i - d, nj = j - (1 - d);\n                    if (ni >= 0 && nj >= 0) {\n                        for (int bal : dp[ni][nj]) {\n                            int nb = bal + (grid[i][j] == '(' ? 1 : -1);\n                            if (nb >= 0) dp[i][j].insert(nb);\n                        }\n                    }\n                }\n            }\n        }\n        return dp[m-1][n-1].count(0);\n    }\n};","lang":"cpp"},{"language":"Python","code":"class Solution:\n    def has_valid_path(self, grid: list[list[str]]) -> bool:\n        m, n = len(grid), len(grid[0])\n        if (m + n - 1) % 2:\n            return False\n        dp = [[set() for _ in range(n)] for _ in range(m)]\n        dp[0][0].add(1 if grid[0][0] == '(' else -1)\n        for i in range(m):\n            for j in range(n):\n                for ni, nj in ((i-1, j), (i, j-1)):\n                    if 0 <= ni < m and 0 <= nj < n:\n                        for bal in dp[ni][nj]:\n                            nb = bal + (1 if grid[i][j] == '(' else -1)\n                            if nb >= 0:\n                                dp[i][j].add(nb)\n        return 0 in dp[m-1][n-1]","lang":"python"},{"language":"Java","code":"class Solution {\n    public boolean hasValidPath(char[][] grid) {\n        int m = grid.length, n = grid[0].length;\n        if ((m + n - 1) % 2 != 0) return false;\n        Set<Integer>[][] dp = new HashSet[m][n];\n        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) dp[i][j] = new HashSet<>();\n        dp[0][0].add(grid[0][0] == '(' ? 1 : -1);\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                for (int[] d : new int[][]{{-1,0},{0,-1}}) {\n                    int ni = i + d[0], nj = j + d[1];\n                    if (ni >= 0 && nj >= 0) {\n                        for (int bal : dp[ni][nj]) {\n                            int nb = bal + (grid[i][j] == '(' ? 1 : -1);\n                            if (nb >= 0) dp[i][j].add(nb);\n                        }\n                    }\n                }\n            }\n        }\n        return dp[m-1][n-1].contains(0);\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun hasValidPath(grid: Array<CharArray>): Boolean {\n        val m = grid.size; val n = grid[0].size\n        if ((m + n - 1) % 2 != 0) return false\n        val dp = Array(m) { Array(n) { mutableSetOf<Int>() } }\n        dp[0][0].add(if (grid[0][0] == '(') 1 else -1)\n        for (i in 0 until m) for (j in 0 until n) {\n            for ((di, dj) in listOf(-1 to 0, 0 to -1)) {\n                val ni = i + di; val nj = j + dj\n                i

Related Tags