括号区间匹配

[编程题]括号区间匹配

热度指数：719 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个由 '[' ，']'，'('，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。

例如当前串是 "([[])"，那么插入一个']'即可满足。

数据范围：字符串长度满足 $1 \le n \le 100 \$

示例1

输入

"([[])"

输出

示例2

输入

"([])()"

输出

算法知识视频讲解

Java

_王泥煤

    public int match (String s) {
        // write code here
        char[] ss = s.toCharArray();
        int[][] dp = new int[ss.length][ss.length];
        for(int i = ss.length-1; i >= 0; --i) {
            dp[i][i] = 1;
            for(int j = i+1; j < ss.length; ++j) {
                if((ss[i] == '[' && ss[j] == ']') || (ss[i] == '(' && ss[j] == ')')) {
                    dp[i][j] = dp[i+1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;
                }
                for(int k = i+1; k < j; ++k) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j]);
                }
            }
        }
        return dp[0][ss.length-1];
    }

发表于 2022-03-04 16:49:56 回复(3)

牛客172608740号

为什么我这个还有两个用例过不不呢，谁能帮忙看一下呢

class Solution:
    def match(self , s: str) -> int:
        m = []
        n = 0
        # write code here
        for i in range(len(s)):

            if s[i] == "("&nbs***bsp;s[i] == "{"&nbs***bsp;s[i] == "[":
                m.append(s[i])
            elif not m:
                n += 1
            elif s[i] == "]":
                j = self.search_from_end(m, "[")
                if j > 0:
                    n += len(m) - j - 1
                    m = m[:j]
                elif j == 0:
                    n += len(m) - j - 1
                    m = []
                else:
                    n += 1
            elif s[i] == ")":
                j = self.search_from_end(m, "(")
                if j > 0:
                    n += len(m) - j - 1
                    m = m[:j]
                elif j == 0:
                    n += len(m) - j - 1
                    m = []
                else:
                    n += 1
            elif s[i] == "}":
                j = self.search_from_end(m, "{")
                if j > 0:
                    n += len(m) - j - 1
                    m = m[:j]
                elif j == 0:
                    n += len(m) - j - 1
                    m = []
                else:
                    n += 1
        n += len(m)
        return n

    def search_from_end(self, lst, item):
        try:
            return len(lst) - lst[::-1].index(item) - 1  # 返回从后向前的索引
        except ValueError:
            return -1

发表于 2024-03-21 23:04:57 回复(1)