Hard
A parentheses string is a non-empty string consisting only of '('
and ')'
. It is valid if any of the following conditions is true:
()
.AB
(A
concatenated with B
), where A
and B
are valid parentheses strings.(A)
, where A
is a valid parentheses string.You are given an m x n
matrix of parentheses grid
. A valid parentheses string path in the grid is a path satisfying all of the following conditions:
(0, 0)
.(m - 1, n - 1)
.Return true
if there exists a valid parentheses string path in the grid. Otherwise, return false
.
Example 1:
Input: grid = [[”(“,”(“,”(“],[”)”,”(“,”)”],[”(“,”(“,”)”],[”(“,”(“,”)”]]
Output: true
Explanation: The above diagram shows two possible paths that form valid parentheses strings.
The first path shown results in the valid parentheses string “()(())”.
The second path shown results in the valid parentheses string “((()))”.
Note that there may be other valid parentheses string paths.
Example 2:
Input: grid = [[”)”,”)”],[”(“,”(“]]
Output: false
Explanation: The two possible paths form the parentheses strings “))(“ and “)((“. Since neither of them are valid parentheses strings, we return false.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j]
is either '('
or ')'
.@Suppress("NAME_SHADOWING")
class Solution {
private lateinit var grid: Array<CharArray>
private var m = 0
private var n = 0
fun hasValidPath(grid: Array<CharArray>): Boolean {
this.grid = grid
m = grid.size
n = grid[0].size
val dp = Array(m) { Array(n) { arrayOfNulls<Boolean>(m + n + 1) } }
if (grid[0][0] == RGTPAR) {
return false
}
return if ((m + n) % 2 == 0) {
false
} else dfs(0, 0, 0, 0, dp)
}
private fun dfs(u: Int, v: Int, open: Int, close: Int, dp: Array<Array<Array<Boolean?>>>): Boolean {
var open = open
var close = close
if (grid[u][v] == LFTPAR) {
open++
} else {
close++
}
if (u == m - 1 && v == n - 1) {
return open == close
}
if (open < close) {
return false
}
if (dp[u][v][open - close] != null) {
return dp[u][v][open - close]!!
}
if (u == m - 1) {
val result = dfs(u, v + 1, open, close, dp)
dp[u][v][open - close] = result
return result
}
if (v == n - 1) {
return dfs(u + 1, v, open, close, dp)
}
val rslt: Boolean
rslt =
if (grid[u][v] == LFTPAR) {
dfs(u + 1, v, open, close, dp) || dfs(u, v + 1, open, close, dp)
} else {
dfs(u, v + 1, open, close, dp) || dfs(u + 1, v, open, close, dp)
}
dp[u][v][open - close] = rslt
return rslt
}
companion object {
private const val LFTPAR = '('
private const val RGTPAR = ')'
}
}