Почему это решение терпит неудачу? Вложенные и соответствующие скобки

Я все еще испытываю недостатки

  • "negative_match: invalid structures," ;
  • "simple_grouped: simple grouped positive and negative test, length=22" ;
  • "large1 simple large positive test, 100K ('s followed by 100K )'s + )(" ;
  • "large2 simple large negative test, 10K+1 ('s followed by 10K )'s + )( + ()" .

Может ли кто-нибудь увидеть, что моя ошибка? Код, который я написал, работает для всех строк, которые я тестировал …

Вот описание задачи:

Строка S состоящая из N символов, считается правильно вложенной, если выполнено одно из следующих условий:

  • S пусто;
  • S имеет форму "(U)" или "[U]" или "{U}" где U – правильно вложенная строка;
  • S имеет форму "VW" где V и W – правильно вложенные строки.

Например, строка "{[()()]}" правильно вложена, но "([)()]" нет.

Напишите функцию:

def solution(S)

что при заданной строке S состоящей из N символов, возвращается 1 если S правильно вложен и 0 противном случае. Например, учитывая S = "{[()()]}" , функция должна возвращать 1 и задавать S = "([)()]" , функция должна возвращать 0 , как объяснялось выше.

Предположим, что:

  • N – целое число в диапазоне [0..200,000] ;
  • строка S состоит только из следующих символов: "(" , "{" , "[" , "]" , "}" и / или ")" .

Сложность : ожидаемая наихудшая временная сложность – O(N) ; ожидаемая наихудшая сложность пространства – O(N) (не считая хранения, необходимого для входных аргументов).

Вот мое решение:

 def solution(S): # write your code in Python 2.7 if S == "": return 1 length = len(S) start = 0 end = length-1 if length%2 != 0: return 0 for i in range(0, length): if (S[start] == '(') and (S[end] != ')'): return 0 if (S[start] == '[') and (S[end] != ']'): return 0 if (S[start] == '{') and (S[end] != '}'): return 0 start = start +1 end = end -1 return 1 pass 

  • Есть ли способ действительно рассортировать скомпилированные регулярные выражения в python?
  • Регулярное выражение Python findall *
  • Как я re.search или re.match для целого файла, не читая все это в памяти?
  • Необязательно получить параметры в django?
  • Более быстрый способ удаления стоп-слов в Python
  • Греп и Питон
  • Как заменить пробелы с подчеркиванием и наоборот?
  • Фильтр Django с регулярным выражением
  • One Solution collect form web for “Почему это решение терпит неудачу? Вложенные и соответствующие скобки”

    Вы ищете слева направо и справа налево – это не сработает ([]{}) – даже если это действительно так, вы можете сравнить [ с } . ( start = 1 и end = 4 )


    В качестве словесного описания я бы сделал следующее:

    • Создайте вторую строку ожидаемых значений. (Объясните это позже)
    • Итерируйте над данной строкой, чтобы создать свою строку ожиданий, когда вы найдете открывающую скобку – сравните, всякий раз, когда вы найдете закрывающую скобку.

    Пример: данная строка является {([])] .

     for i in range(0, length): 
    • IF открывающий кронштейн [ , { , ( помещает ожидаемую закрывающую скобку в конец строки ожидания, т. Е. ] , } Или )
    • ELSE (: = если закрывающая скобка):
      • закрывающая скобка соответствует LAST CHARACTER в строке выписки? -> удалить из строки ожидания, продолжить.
      • закрывающая скобка не соответствует LAST CHARACTER в строке ожидания? -> неверный формат
      • строка ожидания пустая? -> неверный формат
      • Достигнут конец входной строки, строка ожидания НЕ пуста? -> неверный формат.

    Это обработает данную строку следующим образом:

     i | found value | e-string before| e-string after | remark 0 | { | | } | added } 1 | ( | } | }) | added ) 2 | [ | }) | })] | added ] 3 | ] | })] | }) | last element was ] -> removed 4 | ) | }) | } | last element was ) -> removed 5 | ] | } | } | found ] but expected } -> invalid. 

    Изменить: поскольку ожидаемая «Хранение сложности» равно Oh(n) (не считая входных аргументов), вы столкнетесь с сложностью хранения Oh(n) ТОЧНО, тогда, когда данная строка имеет n открывающих скобок – не проблема. Но ты ок. следует использовать вторую string , поэтому в списках есть служебные данные.

    Для сложности выполнения:

    • Установка значения в определенной строковой позиции является атомарной -> Oh(1) (что означает константу )
    • if() являются атомарными -> Oh(1) (что означает константу )
    • Удаление символов является атомарным -> Oh(1) (что означает константу )
    • В вашем цикле for есть Oh(n)зависимости от n )

    Подведите итог, вы получите Oh(n) .


    Если вы хотите реализовать это в Python, вы можете использовать http://dog-net.org/string.php для проверки своих «шагов». 🙂


    ps: Я не предлагаю решение для копирования и вставки специально! :П

    Python - лучший язык программирования в мире.