Class Solution
java.lang.Object
g2201_2300.s2267_check_if_there_is_a_valid_parentheses_string_path.Solution
2267 - Check if There Is a Valid Parentheses String Path.<p>Hard</p>
<p>A parentheses string is a <strong>non-empty</strong> string consisting only of <code>'('</code> and <code>')'</code>. It is <strong>valid</strong> if <strong>any</strong> of the following conditions is <strong>true</strong>:</p>
<ul>
<li>It is <code>()</code>.</li>
<li>It can be written as <code>AB</code> (<code>A</code> concatenated with <code>B</code>), where <code>A</code> and <code>B</code> are valid parentheses strings.</li>
<li>It can be written as <code>(A)</code>, where <code>A</code> is a valid parentheses string.</li>
</ul>
<p>You are given an <code>m x n</code> matrix of parentheses <code>grid</code>. A <strong>valid parentheses string path</strong> in the grid is a path satisfying <strong>all</strong> of the following conditions:</p>
<ul>
<li>The path starts from the upper left cell <code>(0, 0)</code>.</li>
<li>The path ends at the bottom-right cell <code>(m - 1, n - 1)</code>.</li>
<li>The path only ever moves <strong>down</strong> or <strong>right</strong>.</li>
<li>The resulting parentheses string formed by the path is <strong>valid</strong>.</li>
</ul>
<p>Return <code>true</code> <em>if there exists a <strong>valid parentheses string path</strong> in the grid.</em> Otherwise, return <code>false</code>.</p>
<p><strong>Example 1:</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2022/03/15/example1drawio.png" alt="" /></p>
<p><strong>Input:</strong> grid = [[“(”,“(”,“(”],[“)”,“(”,“)”],[“(”,“(”,“)”],[“(”,“(”,“)”]]</p>
<p><strong>Output:</strong> true</p>
<p><strong>Explanation:</strong> The above diagram shows two possible paths that form valid parentheses strings.</p>
<p>The first path shown results in the valid parentheses string “()(())”.</p>
<p>The second path shown results in the valid parentheses string “((()))”.</p>
<p>Note that there may be other valid parentheses string paths.</p>
<p><strong>Example 2:</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2022/03/15/example2drawio.png" alt="" /></p>
<p><strong>Input:</strong> grid = [[“)”,“)”],[“(”,“(”]]</p>
<p><strong>Output:</strong> false</p>
<p><strong>Explanation:</strong> The two possible paths form the parentheses strings “))(” and “)((”. Since neither of them are valid parentheses strings, we return false.</p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>m == grid.length</code></li>
<li><code>n == grid[i].length</code></li>
<li><code>1 <= m, n <= 100</code></li>
<li><code>grid[i][j]</code> is either <code>'('</code> or <code>')'</code>.</li>
</ul>
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
Solution
public Solution()
-
-
Method Details
-
hasValidPath
public boolean hasValidPath(char[][] grid)
-