Блог

Я работаю над решением проблемы генерации круглых скобок в LeetCode. Моей первой мыслью было, что n 1 пара круглых скобок может быть выведена из n пары круглых скобок. Говоря, если мы используем e в качестве ситуации n th, и я подумал n 1 , что th будет одной из следующих ситуаций:

• ( 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 rsu<
    }
}
  

Однако, когда я отправил код, я обнаружил, что все еще пропустил некоторые случаи, когда значение 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 rsu<
    }
}
  

Тем не менее, тестовые примеры завершились неудачно. Так что я в замешательстве. Почему мой способ не работает? Я все еще пропускаю некоторые случаи?

Почему мой способ не работает? Я все еще пропускаю некоторые случаи?

Рассмотрим круглые скобки (())(()) , единственный способ получить это из вашего алгоритма — это if e = ())(() , а затем ( e ) но в этом случае e это неправильно сформированные круглые скобки, поэтому e они никогда не существовали, и вы пропустили случай.

РЕДАКТИРОВАТЬ: казалось бы, ваша вторая редакция решает такие случаи, как ()() , (())(()) , ((()))((())) но как насчет (()())(()()) , или (()())()(()) ?