DDSA Solutions

2267. Check if There Is a Valid Parentheses String Path

HardView on LeetCode
ArrayDynamic ProgrammingMatrix

Problem Overview

A path moves only down or right, so every path from the top left to the bottom right has exactly m + n - 1 cells.

Intuition

A path moves only down or right, so every path from the top left to the bottom right has exactly m + n - 1 cells. What matters at a cell is the balance, the number of opening minus closing parentheses so far. A path is valid when that balance never drops below zero and ends at zero. Each cell only needs the set of balances that can reach it, and that set fits in a row of bits.

Algorithm

  1. 1Return false right away if the path length is odd, the first cell is a closing parenthesis, or the last cell is an opening one.
  2. 2Keep one bitset per column for the current row. Bit k is set when some path reaches that cell with balance k.
  3. 3For each cell, take the union of the bitset above and the bitset to the left. The start cell begins with balance 0 only.
  4. 4An opening parenthesis shifts every balance up by one. A closing parenthesis shifts every balance down by one, and a balance of 0 falls off because it would go negative.
  5. 5After the last cell, the answer is whether balance 0 is still set.

Example Walkthrough

Input: grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]

  1. 1.The path has 4 + 3 - 1 = 6 cells, an even length, so a match is possible.
  2. 2.Going down, down, right, right, down reads ( ) ( ( ) ).
  3. 3.The balance goes 1, 0, 1, 2, 1, 0 and never drops below zero.

Output: true

Common Pitfalls

  • •A balance can never exceed the number of cells left, so the set stays small and the bitset has about (m + n) / 64 words.
  • •Every path into a cell has the same length, which is why one set of balances per cell is enough.
  • •Shifting down must drop the zero bit. Keeping it would accept a prefix with more closing than opening parentheses.
  • •Only one previous row is needed, because a cell reads from the cell above and the cell to its left.
2267.cs
C#
// Approach: Every path into a cell has the same length, so the balance of
// opens minus closes fits in a bitset. Entering '(' shifts that set up by
// one. Entering ')' shifts it down and drops a negative balance. A cell
// keeps the union of the cell above and the cell to the left.
// Complexity: O(mn (m + n) / 64) time, O(n (m + n) / 64) extra space.
public class Solution
{
    public bool HasValidPath(char[][] grid)
    {
        int m = grid.Length;
        int n = grid[0].Length;
        // A valid parentheses string has even length. The path has m + n - 1 cells.
        if (((m + n) & 1) == 0 || grid[0][0] != '(' || grid[m - 1][n - 1] != ')')
            return false;

        int words = (m + n + 63) >> 6;
        ulong[][] dp = new ulong[n][];
        for (int j = 0; j < n; j++)
            dp[j] = new ulong[words];
        ulong[] cell = new ulong[words];

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                Array.Clear(cell);
                if (i == 0 && j == 0)
                    cell[0] = 1UL;
                else
                {
                    if (i > 0)
                        OrInto(cell, dp[j]);
                    if (j > 0)
                        OrInto(cell, dp[j - 1]);
                }

                if (grid[i][j] == '(')
                    ShiftUp(cell);
                else
                    ShiftDown(cell);

                ulong[] previous = dp[j];
                dp[j] = cell;
                cell = previous;
            }
        }

        return (dp[n - 1][0] & 1UL) != 0;
    }

    private static void OrInto(ulong[] dst, ulong[] src)
    {
        for (int i = 0; i < dst.Length; i++)
            dst[i] |= src[i];
    }

    // Balance k moves to k + 1.
    private static void ShiftUp(ulong[] bits)
    {
        ulong carry = 0;
        for (int i = 0; i < bits.Length; i++)
        {
            ulong next = bits[i] >> 63;
            bits[i] = (bits[i] << 1) | carry;
            carry = next;
        }
    }

    // Balance k moves to k - 1. A zero balance falls off and is discarded.
    private static void ShiftDown(ulong[] bits)
    {
        ulong carry = 0;
        for (int i = bits.Length - 1; i >= 0; i--)
        {
            ulong next = bits[i] << 63;
            bits[i] = (bits[i] >> 1) | carry;
            carry = next;
        }
    }
}
Was this solution helpful?

Related Problems