Code Signal – 翻转括号内字符(reverseInParentheses) ?

Write a function that reverses characters in (possibly nested) parentheses in the input string.

Input strings will always be well-formed with matching ()s.

Example:

For inputString = “(bar)”, the output should be reverseInParentheses(inputString) = “rab”;

For inputString = “foo(bar)baz”, the output should be reverseInParentheses(inputString) = “foorabbaz”;

For inputString = “foo(bar)baz(blim)”, the output should be reverseInParentheses(inputString) = “foorabbazmilb”;

For inputString = “foo(bar(baz))blim”, the output should be reverseInParentheses(inputString) = “foobazrabblim”.

Because “foo(bar(baz))blim” becomes “foo(barzab)blim” and then “foobazrabblim”.

Input/Output:

[execution time limit] 4 seconds (js)

[input] string inputString

A string consisting of lowercase English letters and the characters ( and ). It is guaranteed that all parentheses in inputString form a regular bracket sequence.

Guaranteed constraints:

0 ≤ inputString.length ≤ 50.

[output] string

Return inputString, with all the characters that were in parentheses reversed.

解题思路
这道题和之前在 Leetcode 碰到的一个问标点符号的问题感觉很像，所以刚开始打算使用 Stack 去解决这个问题的，后来发现卡在这里了。

主要有以下几个难点：

对于内置函数的返回值不是很熟悉，平常使用 VSC 或者 IDE 开发的时候会打断点、console.log()，但是在做 OA 的时候就很麻烦

主要不是很熟悉的函数有 array.slice()，当只有一个参数 n nn 时，截取的是从 [ n , . . . , l e n g t h − 1 ] [n, …, length – 1][n,…,length−1] 的长度。不知道为什么错误的觉得截取的是 [0, …, n – 1]

过度依赖于之前刷的 Leetcode 的经验，觉得使用 Stack 可以一遍过，但是忽略了两道题的差异。

当时的想法是将 ( 存在 Stack 中，遇到 ) 后就 pop 掉上一个的 ( 所对应的 index，转换 (abcdefg) 中的字符串，再使用一个 counter 去修改原本的数组，以期一个迭代就能完成任务。

如： ab(foo)cd

ab 正常的迭代过去，遇到 (foo) 时，进行翻转，获取 oof，再从下标 2 开始推回原字符串，修改为 aboofo)cd。最后迭代数组，当 stack 的长度为 0 时，将后续的值从 2 + r e v e r s e d S t r . l e n g t h 2 + reversedStr.length2+reversedStr.length 下标开始添加。

这个实现方法的问题就在于，当碰到嵌套字符串时就报错了。

现在想来，加一个检查，当 stack 为空时再去 append 或是 concat 可能会是一个更好的方案。

最终的解决方案还是采取了两个迭代：

翻转所有的字符串

这个基本上跟的就是原本题目的解决方案：

原本的题目：”foo(bar(baz))blim”

根据存在 stack 中的值，首先会翻转最中间的一层：”foo(bar(zab))blim”

随后翻转第二岑：”foo(baz(rab))blim”

去除所有的括号

这个理解起来就比较简单了

因为要做迭代加上翻转，所以这题的时间复杂度为 O ( n 2 ) O(n^2)O(n
2
)，我采用的这个方法空间复杂度为 O ( n ) O(n)O(n)。