在java中生成平衡括号 [英] Generate balanced parentheses in java

问题描述

问题是：
给定n对括号，编写一个函数来生成格式正确的括号的所有组合。

The question is: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

例如，给定n = 3，解决方案集是：

For example, given n = 3, a solution set is:

（（（））），（（）（）），（（））（）， （）（（）），（）（）（）

"((()))", "(()())", "(())()", "()(())", "()()()"

我曾经使用字符串解决这个问题如下：

I used to solve this problem using string as following codes:

public class Solution {
public List<String> generateParenthesis(int n) {

    ArrayList<String> result = new ArrayList<String>();
    //StringBuilder s = new StringBuilder();
    generate(n, 0, 0, "", result);
    return result;
}
public void generate(int n, int left, int right, String s, ArrayList<String> result){

    //left is num of '(' and right is num of ')'
    if(left < right){
        return;
    }
    if(left == n && right == n){
        result.add(s);
        return;
    }
    if(left == n){
        //add ')' only.
        generate(n, left, right + 1, s + ")", result);
        return;
    }
    generate(n, left + 1, right, s + "(", result);
    generate(n, left, right + 1, s + ")", result);
    }
}

现在我想用StringBuilder解决这个问题，代码是这样的：

Now I want to solve this problem using StringBuilder, the code is like this:

import java.util.ArrayList;

public class generateParentheses {
public static ArrayList<String> generateParenthesis(int n) {

    ArrayList<String> result = new ArrayList<String>();
    StringBuilder sb = new StringBuilder();

    generate(n, 0, 0, result, sb);
    return result;
}

public static void generate(int n, int left, int right, ArrayList<String> result,
        StringBuilder sb) {

    if (left < right) {
        return;
    }
    if (left == n && right == n) {
        result.add(sb.toString());
        sb = new StringBuilder();
        return;
    }
    if (left == n) {
        generate(n, left, right + 1, result, sb.append(')'));
        return;
    }
    generate(n, left + 1, right, result, sb.append('('));
    //sb.delete(sb.length(), sb.length() + 1);
    generate(n, left, right + 1, result, sb.append(')'));
    //sb.delete(sb.length(), sb.length() + 1);
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println(generateParenthesis(4));
    }
}

结果不是我想要的：
（（（（）））），（（（（（）））））（））），（（（（）））））（））））（）），（（（（）））） ））（））））（）））（），（（（（）））））（））））（）））（）））（（））），（（（（））））） （））））（）））（）））（（））））（））.........

The result is not what I want: (((()))), (((()))))())), (((()))))())))()), (((()))))())))()))(), (((()))))())))()))()))(())), (((()))))())))()))()))(())))()).........

有没有人告诉我有什么问题？非常感谢。

Is there anyone tell me what is the problem? Thank you very much.

推荐答案

您关闭。你的错误：

• 试图重置 sb 而不是只删除它的最后一个字符



• 您要重置的方式 sb ：

• trying to reset sb instead of removing only its last character

• way you want to reset sb:

• 使用 sb = new StringBuilder（）; 你要重新分配 sb 这是本地变量当前方法，而不是调用它的方法的变量（Java不是通过引用传递而是按值传递）。



• 你几乎正确的尝试仓库评论 sb.delete（sb.length（），sb.length（）+ 1）; 但是在这里你实际上是想从位置<$开始删除字符c $ c> sb.length（），但就像StringBuilder中字符的数组索引是从 0 到 sb .length（） - 1 所以试图在最后一个字符后删除一个字符，实际上无法删除任何内容。

• by using sb = new StringBuilder(); you are reassigning sb which is local variable of current method, not variable of method which invoked it (Java is not pass-by-reference but pass-by-value).

• your almost correct attempt ware commented sb.delete(sb.length(), sb.length() + 1); but here you are actually trying to remove characters starting from position sb.length(), but just like arrays indexes of character in StringBuilder are from 0 till sb.length() - 1 so is trying to remove one character after last character which effectively can't remove anything.

这里需要的是

sb.delete(sb.length() - 1, sb.length());

或更具可读性

sb.deleteCharAt(sb.length() - 1);

但在性能方面可能是最好的方法 setLength （在答案底部描述）

but probably best approach in terms of performance setLength (described at bottom of answer)

sb.setLength(sb.length() - 1); 

的逻辑当从StringBuilder中删除字符时也有缺陷

your logic of when to remove characters from StringBuilder is also flawed

• 你只在一个地方结束（回溯） ）递归调用：找到正确的结果后。但是其他情况如 if（left< right）或 最重要的是，如果方法正常结束

• you are doing it only in one place which ends (backtracks) recursive calls: after finding correct results. But what about other cases like if (left < right) or most importantly, if method will end normally like

generate(3, 1, 1, ')');
generate(3, 1, 2, ')');//here we stop and backtrack

这里生成（3,1,2，'）'）; 结束并删除 sb 中的最后一个字符，但不应该是以前的方法 generate（3,1,1，'）'）也删除自己的）添加到StringBuilder？

Here generate(3, 1, 2, ')'); ends and removes last character from sb, but shouldn't previous method generate(3, 1, 1, ')') also remove its own ) added to StringBuilder?

换句话说，只有在递归调用成功条件结束时才应删除最后一个字符，但在每次递归调用之后，要确保该方法也会删除它添加的字符。

In other words you shouldn't remove last character only at end of successful condition in recursive call, but after each recursive call, to make sure that method will also remove character it adds.

所以更改你的代码类似

public static void generate(int n, int left, int right, ArrayList<String> result,
        StringBuilder sb) {

    if (left < right) {
        return;
    }
    if (left == n && right == n) {
        result.add(sb.toString());
        return;
    }
    if (left == n) {
        generate(n, left, right + 1, result, sb.append(')'));
        sb.deleteCharAt(sb.length() - 1);// <--
        return;
    }
    generate(n, left + 1, right, result, sb.append('('));
    sb.deleteCharAt(sb.length() - 1);// <--
    generate(n, left, right + 1, result, sb.append(')'));
    sb.deleteCharAt(sb.length() - 1);// <--
}

或尝试写一些可能更具可读性的内容，如

or try writing something probably more readable like

public static void generate(int maxLength, int left, int right,
        ArrayList<String> result, StringBuilder sb) {
    if (left + right == maxLength) {
        if (left == right)
            result.add(sb.toString());
    } else if (left >= right) {
        generate(maxLength, left + 1, right, result, sb.append('('));
        sb.deleteCharAt(sb.length() - 1);

        generate(maxLength, left, right + 1, result, sb.append(')'));
        sb.deleteCharAt(sb.length() - 1);
    }
}

但在调用时需要设置 maxLength as 2 * n 因为它是StringBuilder应该包含的最大长度，所以你还必须更改 generateParenthesis（int n） to：

but while invoking you would need to set maxLength as 2*n since it is the max length StringBuilder should contain, so you would also have to change generateParenthesis(int n) to:

public static ArrayList<String> generateParenthesis(int n) {

    ArrayList<String> result = new ArrayList<String>();
    StringBuilder sb = new StringBuilder(2 * n);

    generate(2 * n, 0, 0, result, sb);
    //       ^^^^^
    return result;
}

---

进一步改善：

如果您的目标是性能，那么您可能不想使用 delete 或 deleteCharAt 因为每次创建新数组并使用您不想要的值的副本填充它。

If you are aiming for performance then you probably don't want to use delete or deleteCharAt because each time it creates new array and fills it with copy of values from without ones you don't want.

相反，您可以使用 setLength 方法。如果您将传递小于当前存储字符数的值，则会将 count 设置为此方法中传递的值，这将有效地使其后的字符无关紧要。换句话说，这些字符将不再用于例如 toString（），即使它们仍然在StringBuilder缓冲区数组中。

Instead you can use setLength method. If you will pass value which is smaller than number of currently stored characters it will set count to value passed in this method, which will effectively make characters after them irrelevant. In other words this characters will be no longer used in for instance toString() even if they will be still in StringBuilder buffer array.

示例：

StringBuilder sb = new StringBuilder("abc");  // 1
sb.setLength(2);                              // 2
System.out.println(sb);                       // 3
sb.append('d');                               // 4
System.out.println(sb);                       // 5

• 第1行 StringBuilder 将为至少 3 字符分配数组（默认使用 str.length（）+ 16 确定它现在将存储的缓冲字符数组的大小）并将放置来自传递的字符串的字符，因此它将包含

  • In line 1 StringBuilder will allocate array for at least 3 characters (by default it uses str.length() + 16 to determine size of buffered array of characters it will store for now) and will place there characters from passed String, so it will contain

    ['a', 'b', 'c', '\0', '\0', ... , '\0']
                     ^^^ - it will put next character here 
    

    应该放置下一个字符的位置索引存储在<$ c $中c> count 字段，现在它等于 3 。

    Index of position where next character should be placed is stored in count field and for now it is equal to 3.

    在第2行中， count 的值将设置为 2 ，但我们的数组不会被更改，因此它仍然会看起来像

    In line 2 value of count will be set to 2, but our array will not be changed so it will still look like

    ['a', 'b', 'c', '\0', '\0', ... , '\0']
               ^^^ - it will put next character here 
    

  
  

  • 在第3行中，将创建并打印新的String，但只会在索引前放置字符存储在 count 中，这意味着它只包含 a 和 b （数组仍将保持不变）。

  • In line 3 new String will be created and printed, but it will be filled only with characters placed before index stored in count, which means that it will contain only a and b (array will still be unchanged).

    在第4行中，您将向缓冲区添加新字符，它将放在重要字符之后。由于重要字符的数量存储在 count 字段中（并且它们位于数组的开头），因此下一个不相关的字符必须位于指向的位置，这意味着 d 将被放置在索引 2 的位置，这意味着现在数组将看起来像

    In line 4 you will add new character to buffer and it will be placed after "important" characters. Since number of important characters is stored in count field (and they are placed at beginning of array), next irrelevant character must be at position pointed by count, which means d will be placed at position with index 2 which means now array will look like

    ['a', 'b', 'd', '\0', '\0', ... , '\0']
                     ^^^ - it will put next character here 
    

    和 count 的值将递增（我们只添加了一个字符，因此 count 现在将变为 3 ）。

    and value of count will be incremented (we added only one character so count will now become 3).

    这篇关于在java中生成平衡括号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！