В этой задаче LeetCode нам предоставляется строка скобок (( и )) и предлагается найти длину самой длинной допустимой подстроки скобок. Действительный определяется как правильно открытый и закрытый набор круглых скобок, таких как (), (()), ()() и т. д.
Решение № 1: найти все допустимые возможности
Это условно известно как метод грубой силы и, безусловно, является самым медленным допустимым вариантом. В этом подходе мы перебираем предоставленную строку и создаем «потенциально допустимую строку» (PVS) каждый раз, когда встречаем открывающие скобки. Затем мы продолжаем обход строки до тех пор, пока указанный PVS не будет правильно закрыт, после чего мы считаем PVS действительным и возвращаем самый длинный из найденных.
Хотя это проще всего объяснить, это, к сожалению, наиболее неэффективно, поскольку мы не только храним больше данных, но и выполняем гораздо больше вычислений, чем следующий подход.
Решение № 2. Определение неправильных символов
Этот подход (который вдохновлен рядом плакатов, но преимущественно флорибон с его представлением) делает противоположное вышеизложенному, вместо этого ищет все недопустимые скобки. Как только мы узнаем все недопустимые скобки, мы можем предположить, что строки между упомянутыми недопустимыми скобками допустимы, и, таким образом, вычислить самую большую из тех.
С вычислительной точки зрения этот подход намного лучше, но его определенно сложнее понять, и он основан на допущении, которое не кажется полностью интуитивным (но, очевидно, правильным, по крайней мере, в тестовых примерах, предоставленных LeetCode).
