在LeetCode中生成小括號

Question

我正在解決問題Generate Parentheses on LeetCode。我首先想到的是，第012對括號可以從n第二對括號中推導出來。他說，如果我們使用e作爲n日的情況，我認爲n+1日將是以下情況之一：

• ( + e + )
• () + e
• e + ()

我想出了下面的代碼。

public class Solution { 
    public List<String> generateParenthesis(int n) { 
     HashSet<String> temp = new HashSet<String>(); 
     HashSet<String> result = new HashSet<String>(); 
     List<String> rsult = new ArrayList<String>(); 

     if (n == 0) { 
      temp.add(""); 
      return new ArrayList<String>(temp); 
     } 

     temp.add("()"); 

     if (n == 1) { 

      return new ArrayList<String>(temp); 
     } 

     for (int i = 2; i <= n; i++) { 
      result.removeAll(temp); 
      for (String e : temp) { 
       if (!result.contains("(" + e + ")")) { 
        result.add("(" + e + ")"); 
       } 

       if (!result.contains("()" + e)) { 
        result.add("()" + e); 
       } 

       if (!result.contains(e + "()")) { 
        result.add(e + "()"); 
       } 

      } 

      temp.clear(); 
      temp.addAll(result); 
     } 
     rsult = new ArrayList<String>(result); 
     Collections.sort(rsult); 
     return rsult; 
    } 
} 

然而，當我提交的代碼，我發現，我還是錯過了一些情況下，當n+1是偶數。所以我更新了我的代碼如下。

public class Solution { 
    public List<String> generateParenthesis(int n) { 
     HashSet<String> temp = new HashSet<String>(); 
     HashSet<String> result = new HashSet<String>(); 
     List<String> rsult = new ArrayList<String>(); 

     if (n == 0) { 
      temp.add(""); 
      return new ArrayList<String>(temp); 
     } 

     temp.add("()"); 

     if (n == 1) { 

      return new ArrayList<String>(temp); 
     } 

     for (int i = 2; i <= n; i++) { 
      result.removeAll(temp); 
      for (String e : temp) { 
       if (!result.contains("(" + e + ")")) { 
        result.add("(" + e + ")"); 
       } 

       if (!result.contains("()" + e)) { 
        result.add("()" + e); 
       } 

       if (!result.contains(e + "()")) { 
        result.add(e + "()"); 
       } 

       if (i % 2 == 0) { 
        String dblprt = new String(); 
        for(int j = 0; j< i/2;j++) { 
         dblprt = "(" + dblprt + ")"; 
        } 
        dblprt = dblprt + dblprt ; 
        if (!result.contains(dblprt)) { 
         result.add(dblprt); 
        } 
       } 
      } 

      temp.clear(); 
      temp.addAll(result); 
     } 
     rsult = new ArrayList<String>(result); 
     Collections.sort(rsult); 
     return rsult; 
    } 
} 

但是，測試用例失敗。所以我很困惑。爲什麼我的方式不行？我還錯過了一些情況嗎？

Answer 1

爲什麼我的方式不行？我還錯過了一些情況嗎？

考慮括號(())(())，這樣做的唯一方法來從你的算法是，如果e =())(()，然後( + e + )，但在這種情況下e不是一個結構良好的括號以e從未存在過和你錯過了一個案子。

編輯：它似乎是你的第二個版本解決的情況下，如()()，(())(())，((()))((()))但對於(()())(()())，或(()())()(())？