Leetcode每日一题 —— 2267. 检查是否有合法括号字符串路径

用记忆化 DFS 写的话，思路很清晰。

class Solution {

public:

    bool hasValidPath(vector<vector<char>>& grid) {

        // 只要存在一条合法的就行

        // 因为从左上角开始，右下角结束，路径长度总是相同的

        // 过程中左括号数量肯定 >= 右括号数量

        // 直接 DFS

        bool res=false;

        int m=grid.size(),n=grid[0].size();

        if(((m+n-1)&1)==1){

            // 路径长度为奇数，不可能

            return false;

        }

        bool visited[m][n][m+n-1];

        memset(visited,0,sizeof(visited));

        auto dfs=[&](this auto&& self,int row,int col,int left) -> void {

            if(res)

                return;

            if(visited[row][col][left]) // 不重复访问相同状态

                return;

            visited[row][col][left]=true;

            if(grid[row][col]=='('){

                left++;

            }else if(grid[row][col]==')'){

                left--;

            }

            // cout<<"ROW: "<<row<<" COL: "<<col<<" LEFT: "<<left<<endl;

            if(left<0){

                // 左括号数量 < 右括号数量

                return;

            }

            if(left==0&&row==m-1&&col==n-1){

                res=true;

                return;

            }

            // 要不往右要不往下走

            if(col<n-1){

                self(row,col+1,left);

            }

            if(row<m-1){

                self(row+1,col,left);

            }

        };

        dfs(0,0,0);

        return res;

    }

};

按理来说这个级别的题目不该hard。不过依然慢..

class Solution {

public:

    bool hasValidPath(vector<vector<char>>& grid) {

        int m = grid.size(),n = grid[0].size();

        vector<vector<vector<bool>>> f(m + 1,vector<vector<bool>>(n + 1,vector<bool>((n + m + 3) / 2,false)));

        f[0][1][0] = true;

        for(int i = 1; i <= m; i++) {

            for(int j = 1; j <= n; j++) {

                for(int k = 0; k < (n + m + 1) / 2; k++) {

                    int val = grid[i - 1][j - 1] == '(' ? 1 : -1;

                    if(k - val >= 0) {

                        f[i][j][k] = f[i - 1][j][k - val] | f[i][j - 1][k - val];

                    }

                }

            }

        }

        return f[m][n][0];

    }

};

// ( = 1 , ) = -1, to get 0, and min(prefix_sum) >= 0

可以bitset加速

class Solution {

public:

    bool hasValidPath(vector<vector<char>>& mp) {

        int i,j,n,m;

        bitset<105> f[105][105];

        n=mp.size(); m=mp[0].size();

        f[0][1][0]=1;

        for(i=1;i<=n;i++)for(j=1;j<=m;j++){

            f[i][j]=(f[i-1][j]|f[i][j-1]);

            if(mp[i-1][j-1]=='(')f[i][j]<<=1;

            else f[i][j]>>=1;

        }

        return f[n][m][0];

    }

};

Kotlin每日打卡（DFS+剪枝）：

class Solution {

    fun hasValidPath(grid: Array<CharArray>): Boolean {

        val m = grid.size

        val n = grid[0].size

        if ((m + n) % 2 == 0 || grid[0][0] == ')' || grid[m - 1][n - 1] == '(') {

            return false

        }



        val vis = Array(m) { Array(n) { BooleanArray((m + n + 1) / 2) } }

        return dfs(0, 0, 0, grid, vis)

    }



    private fun dfs(x: Int, y: Int, count: Int, grid: Array<CharArray>, vis: Array<Array<BooleanArray>>): Boolean {

        val m = grid.size

        val n = grid[0].size

        if (count > m - x + n - y - 1) {

            return false

        }

        if (x == m - 1 && y == n - 1) {

            return count == 1

        }



        if (vis[x][y][count]) {

            return false

        }

        vis[x][y][count] = true



        val nextCount = count + if (grid[x][y] == '(') 1 else -1

        if (nextCount < 0) {

            return false

        }

        return x < m - 1 && dfs(x + 1, y, nextCount, grid, vis) ||

               y < n - 1 && dfs(x, y + 1, nextCount, grid, vis)

    }

}

思路：滚动 DP + 位集优化

#include <stdbool.h>

#include <stdint.h>

#include <string.h>



bool hasValidPath(char** grid, int gridSize, int* gridColSize) {

    int m = gridSize, n = gridColSize[0], len = m + n - 1;

    if ((len & 1) || grid[0][0] == ')' || grid[m - 1][n - 1] == '(')

        return false;



    int k = (len / 2 + 64) / 64;

    uint64_t dp[n][k], cur[k];

    memset(dp, 0, sizeof(dp));

    dp[0][0] = 1;



    for (int i = 0; i < m; ++i) {

        for (int j = 0; j < n; ++j) {

            for (int t = 0; t < k; ++t)

                cur[t] = dp[j][t] | (j ? dp[j - 1][t] : 0);



            for (int t = 0; t < k; ++t) {

                if (grid[i][j] == '(')

                    dp[j][t] = (cur[t] << 1) | (t ? cur[t - 1] >> 63 : 0);

                else

                    dp[j][t] =

                        (cur[t] >> 1) | (t + 1 < k ? cur[t + 1] << 63 : 0);

            }

        }

    }

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

}

擦车+剪枝提前退出，也可以继续优化成递推dp（但是懒了 ^-^

class Solution:

    def hasValidPath(self, grid: List[List[str]]) -> bool:

        m, n = len(grid), len(grid[0])

        if (m + n) % 2 == 0 or (grid[0][0] == ')') or (grid[-1][-1] == '('):

            return False

        @cache

        def dfs(i, j, c):

            if c > (m - i) + (n - j) - 1:

                return False

            if i == m - 1 and j == n - 1:

                return c == 1



            c += 1 if grid[i][j] == '(' else -1

            if c < 0:

                return False



            return (i + 1 < m and dfs(i + 1, j, c)) or \

                (j + 1 < n and dfs(i, j + 1, c))

        

        return dfs(0, 0, 0)