Цитата(Metrax @ 29.10.2006 12:06)
![*](style_images/1/post_snapback.gif)
ето самое последнее мое решение, вродь лучше и ниможет быть, почему непроходит по времени????? напишите свои решегия... заранее благодарен
Твое решение имеет квадратичную сложность. Ты все делаешь одним линейным циклом, но процедура delete работает тоже за линейное время; меняя строку (потенциально на каждой итерации), ты замедляешься до квадрата.
На самом деле тебе строку менять не надо. Суть твоего алгоритма: идем слева направо, как только нашли "()" - удаляем из строки, откатываем на 1 позицию влево, и продолжаем поиск.
То же самое можно сделать несколько по-другому. Идем слева направо. Храним счетчик количества открытых скобок, и счетчик "лишних" скобок. В начале оба равны 0. Встретив открытую скобку, увеличиваем счетчик открытых. Встретив закрытую, проверяем счетчик открытых. Если он больше нуля, уменьшаем его на 1 (нашли "()"). Если же он равен нулю, это значит, что встреченная закрывающая скобка - лишняя. Увеличиваем счетчик "лишних". Дойдя до конца строки, добавляем значение счетчика открытых скобок к счетчику "лишних" (потому что эти открытые так и не закрылись).
Т.е. я не менял идеи твоего алгоритма, но перешел от изменения строки к запоминанию промежуточных результатов. Пробуй, должно пройти.