Category Archives: LeetCode

LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

题意

每层括号里面的东西需要反转一次。即在在偶数层括号里面的字符是正序的,在奇数层括号里面的字符是逆序的。然后拼成结果。

例子:

"(abcd)"
反转之后就是:
cdba
"(u(love)i)"
love不反转,u,love,i三个反转,答案为:
iloveu

思路

网上有人直接用栈存储,每一个元素代表当前层级括号中的字符串,如果遇到括号关闭,将当前层级字符串反转再append到上一级的字符串中。

但是,括号层级一多,字符串反转的次数就非常多了。而且很多反转都是没有必要的。

其实直接递归就好,或者说分治:

每个括号内部都算作独立的子问题,如果正… Read the rest