Skip to content

Latest commit

 

History

History
 
 

1190.Reverse-Substrings-Between-Each-Pair-of-Parentheses

1190.Reverse-Substrings-Between-Each-Pair-of-Parentheses

解法1:模拟

模拟整个过程。字符串ret只记录字母,用栈来标记左右括号的配对。

遇到左括号时,往栈推入当前ret的长度。遇到右括号时,从栈顶读取的index,它就是ret里与之配对的“虚拟的”左括号的位置。然后将index到ret末尾的字符串整体翻转。不断重复以上操作即可。

举个例子:

abc(def(ghi)k)
   ^   ^
  1. 第一次遇到右括号之前,ret = "abcdefghi",栈里面的元素是[3,6]. 遇到第一个右括号时,说明ret[6,end]需要翻转,得到ret = "abcdefihg",
  2. 第二次遇到右括号之前,ret = "abcdefihgk",栈里面的元素是[3]. 遇到第二个右括号时,说明ret[3,end]需要翻转,得到ret = "abckghifed",就是最终的答案。

考虑到很多字母被加入ret之后又要逆序,所以时间复杂度是o(N^2)。

解法2:反向模拟

还是上述的例子,当我们顺着读取abc后看到跟在后面的(....)时,知道括号内def(ghi)k解析之后的结果一定最终是会反向输出的,那么索性我们就反向读取他们,即从k开始往前读。怎么找到的k呢?那就是从这个左括号对应的右括号开始往左走。

然后,我们又碰到一个更深一级的括号,里面是ghi。同理我们知道这个更深一层的括号依然会使内部的东西最终反向输出,那么我们就索性继续反向读取它们,即从g开始往右读。怎么找到的g呢?那就是从这个右括号对应的左括号,然后开始往右走。于是就顺次ghi都读完了。

再接着,我们碰到了右括号。此时应该干什么呢?此时这对括号读完了,应该继续之前被暂停的f。怎么快速定位到f呢?其实就是再跳回原来的左括号,但此时继续往左走。

于是我们发现了一个规律。当你进入一层更深的括号时,就跳到括号的另一边反向读取。当你离开该层括号时,也要跳到括号的另一边反向离开。

所谓“进入一层更深的括号”,包括(1)从左往右进入左括号,此时你需要跳转至右括号然后往左读取括号内的内容;(1)从右往做进入右括号,此时你需要跳转至左括号然后往右读取括号内的内容;

所谓“离开该层的括号”,包括(1)从左往右进入右括号,此时你需要跳转至左括号然后往左读取括号外的内容;(1)从右往做进入左括号,此时你需要跳转至右括号然后往右读取括号外的内容;

同上以上的顺序,我们就可以用o(N)的时间走遍整个字符串。