Java 中的有效括号问题

我们接收到一个字符串输入 inputStr。该字符串 inputStr 只包含 '[', ']', '{', '}', '(', 和 ')'。我们的任务是确定字符串 inputStr 是否有效。字符串有效需要满足以下标准。

• 每个开括号都应由相同类型的括号关闭。
• 括号关闭的顺序必须是正确的。
• 每个闭括号都应映射到具有相同类型的对应开括号。显而易见，闭括号应出现在开括号之后。

示例 1

输入

字符串 inputStr = "(())"

输出： 输入字符串是有效字符串。

解释： 开括号已正确关闭，即顺序正确。因此，给定的字符串是有效字符串。

示例 2

输入

字符串 a1 = "(({)})"

输出： 输入字符串不是有效字符串。

解释： 花括号 { 已正确打开。但在闭合花括号 } 之前，我们有闭合圆括号 )。因此，给定的字符串不是有效字符串。

示例 3

字符串 a1 = "(({}))"

输出： 输入字符串是有效字符串。

解释： 所有括号都已正确打开和关闭。因此，给定的字符串是有效输入字符串。

示例 4

字符串 a1 = ")([{}])"

输出： 输入字符串不是有效字符串。

解释： 除一个外，所有括号都已正确打开和关闭。但是，最后一个括号是一个开着的圆括号，并且没有正确映射到闭合圆括号。因此，给定的字符串不是有效的输入字符串。

示例 5

字符串 a1 = "()(({}))("

输出： 输入字符串不是有效字符串。

解释： 除一个外，所有括号都已正确打开和关闭。但是，最后一个括号是一个开着的圆括号，并且没有正确映射到闭合圆括号。因此，给定的字符串不是有效的输入字符串。

方法

显然，每个开括号都有对应的闭括号。因此，字符串中的括号数量应该是偶数，这可以作为我们的基本情况。我们可以拒绝大小不是偶数的字符串。对于大小为偶数的字符串，我们需要检查每个开括号是否具有对应的（相同类型的）闭括号。如果可用，则字符串有效；否则无效。

要检查每个开括号，我们可以使用递归或迭代。让我们首先使用递归方法来解决这个问题。

文件名： ValidString.java

输出

The string "(())" is a valid string.

The string "(({)})" is not a valid string.

The string "(({}))" is a valid string.

The string ")([{}])" is not a valid string.

The string "()(({}))(" is not a valid string.

复杂度分析： 最多，字符串的每个字符只会被遍历一次。因此，程序的时间复杂度为 O(N)。此外，递归调用之后的语句会进入堆栈，使程序的空间复杂度为 O(N)，其中 N 是输入字符串中存在的字符总数。

现在让我们看看迭代实现。

实现：使用堆栈

文件名： ValidString1.java

输出

The string "(())" is a valid string.

The string "(({)})" is not a valid string.

The string "(({}))" is a valid string.

The string ")([{}])" is not a valid string.

The string "()(({}))(" is not a valid string.

复杂度分析： 该程序的时间复杂度和空间复杂度与上一个程序相同。