Создание скобок в LeetCode

Question

Я работаю над решением проблемы Generate Parentheses on LeetCode. Моя первая мысль заключалась в том, что n+1-я пара круглых скобок может быть выведена из 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 никогда не существовало и вы пропустили дело.

EDIT: казалось бы, что ваша вторая редакция решает такие случаи, как ()(), (())(()), ((()))((())), но как насчет (()())(()()) или (()())()(())?