面对理解以下算法解决方案的问题



我是Hacker Rank的新手,目前正在解决java堆栈中的问题,我尝试解决此算法:

如果满足以下条件,则仅包含括号的字符串是平衡的:1. 如果它是空字符串 2. 如果 A 和 B 正确,则 AB 正确,3. 如果 A 正确,则 (A) 和 {A} 和 [A] 也正确。

一些正确平衡的字符串的示例包括:"{}()", "[{()}]", "({()})">

一些不平衡字符串的示例包括:"{}(", "({)}", "[[", "}{" 等。

给定一个字符串,确定它是否平衡。


我找到了以下一个我无法理解的衬里解决方案,有人可以解释一下吗?

class Solution{
public static void main(String []argh)
{
Scanner sc = new Scanner(System.in);

while (sc.hasNext()) {
String input=sc.next();
while(input.length() != (input = input.replaceAll("\(\)|\[\]|\{\}", "")).length());
System.out.println(input.isEmpty());
}

}
}

"\(\)|\[\]|\{\}"给定replaceAll的字符串是一个正则表达式。需要一半的反斜杠,因为所有反斜杠()[]{}正则表达式中都有特殊含义;另一半需要转义这些反斜杠,因为它在字符串中具有特殊含义。

忽略反斜杠,模式()|[]|{},这将匹配任何子字符串()[]{}。然后,replaceAll调用通过用空字符串""替换它们来删除它们的所有匹配项。然后重复此操作,直到无法替换更多匹配项。

在平衡字符串上,并且仅在平衡字符串上,这最终通过从内到外删除空对来生成空字符串。让我们看一个例子:

[{()}]()[{}]
^^  ^^ ^^  <- these matches are removed
[{}][]
^^ ^^ <- then these are removed
[]
^^ <- and finally this one

while循环的编写方式还存在一些混淆:

while(input.length() != (input = input.replaceAll(...)).length());

要理解这一点,您需要知道=执行分配,但也计算分配的值。而且你需要知道Java总是从左到右计算子表达式。

因此,首先,input.length()被计算,生成原始字符串的长度。然后计算(input = input.replaceAll(...)).length(),它做两件事:它将下一个字符串分配给input,并返回下一个字符串的长度。

最后,比较两种长度。如果相等,则循环终止,因为没有更多内容可以替换。如果不相等,则表示已删除某些匹配对,我们将进行另一次迭代,现在使用新值input

最后,我们只检查结果字符串是否为空:

System.out.println(input.isEmpty());

替换所有方法需要 2 个参数(正则表达式、替换); 您需要了解正则表达式:

\意味着无论开始是什么。(\)开始必须是'('的,结束必须是')'的,无论它们之间有什么,就像从正则表达式中休息一样。

解决方案是用空字符串替换正则表达式。

因此,如果您的input = (1,2)3(,它将是在更换3(之后

最新更新