CodeSignal reverseParentheses 失败一种情况

Question

编写一个函数来反转输入字符串中（可能嵌套的）括号中的字符。

输入字符串将始终格式正确且具有匹配 ()s。

对于inputString = "(bar)"，输出应该是 reverseInParentheses(inputString) = "rab";
对于inputString = "foo(bar)baz"，输出应该是 reverseInParentheses(inputString) = "foorabbaz";
对于inputString = "foo(bar(baz))blim"，输出应该是 reverseInParentheses(inputString) = "foobazrabblim".

[input] 字符串 inputString

一个由小写英文字母和字符（和）组成的string。保证inputString中的所有括号组成一个正则括号序列

保证约束：

0 ≤ inputString.length ≤ 50.

[输出]字符串

Return inputString，将括号中的所有字符反转。

我的解决方案

Java 脚本

function reverseInParentheses(inputString) {
    let arr = inputString
    let start = arr.indexOf(')') < arr.lastIndexOf('(') ? arr.indexOf('(') : arr.lastIndexOf('(')
    let end = arr.indexOf(')')
    
    let temp = arr.substring(start + 1, end)
    if(start !== -1 && end !== -1){
        return reverseInParentheses(arr.substring(0, start) + 
        [...temp].reverse().join('') + 
        arr.substring(end + 1))
    }
    return arr
}

问题

我正在通过除最终隐藏案例之外的所有案例，没有返回运行时或执行时间限制错误。所以我无法弄清楚是什么情况导致了失败。我真的很想使用我自己的解决方案而不是复制正则表达式的解决方案，并且在我看来这个解决方案应该有效，也许更有经验的人可以证明我的愚蠢。提前致谢。

Answer 1

问题是你计算的 start 和 end 真的不行。这个问题没有简单的解决办法。

Jonas Wilms 的评论建议尝试 '((see)(you))'。对于此测试用例，您将得到 start 和 end，如下所示：

          0    5
          ((see)(you))
          ^    ^
start ----'    '---- end

请注意，这里的开始和结束并不是真正的一对。中间还有一个'('。

您可以通过对这些值进行更复杂的计算来解决此问题，方法是遍历字符，每次点击 '(' 时更新 start 并更新 end你打了 ')'，然后停止了。

可能看起来像这样：

function reverseInParentheses(inputString) {
    let arr = inputString
    let i = 0, start = 0, end = -1
    while (end < start && i < arr.length) {
        if (arr[i] == '(') {start = i}
        if (arr[i] == ')') {end = i}
        i++
    }
   
    let temp = arr.substring(start + 1, end)
    if(start !== -1 && end !== -1){
        return reverseInParentheses(arr.substring(0, start) + 
        [...temp].reverse().join('') + 
        arr.substring(end + 1))
    }
    return arr
}

console .log (reverseInParentheses('(bar)'))
console .log (reverseInParentheses('foo(bar)baz'))
console .log (reverseInParentheses('foo(bar(baz))blim'))
console .log (reverseInParentheses('((see)(you))'))

我不是特别喜欢这个，将迭代查找括号与递归相结合，以不断重新应用该函数，直到剩下 none。感觉很尴尬。

如您所述，还有其他解决方案。一种是使用正则表达式。请注意，平衡括号的语言不是常规语言，因此不能被任何一个正则表达式捕获，但您可以在迭代或递归中重复应用正则表达式操作以使其工作。这是其中一个版本。

const rev = ([...cs]) => cs.reverse().join('')

const reverseInParentheses = (s) =>
  /\(([^)]*)\)/ .test (s) 
    ? reverseInParentheses (s .replace(/(.*)\(([^)]*)\)(.*)/, (_, a, b, c) => a + rev(b) + c)) 
    : s

console .log (reverseInParentheses('(bar)'))
console .log (reverseInParentheses('foo(bar)baz'))
console .log (reverseInParentheses('foo(bar(baz))blim'))
console .log (reverseInParentheses('((see)(you))'))

简而言之，这会找到最里面的一对括号，将它们替换为内容的反转，然后在结果上重复出现，当找不到更多对时触底。

这个解决方案被放在一起，可能有更好的正则表达式操作可用。

但实际上我更喜欢完全不同的方法，将字符串的字符视为简单状态机的事件，并带有一堆嵌套的带括号的子字符串。这是我写的：

const reverseInParentheses = ([c, ...cs], res = ['']) =>
  c == undefined 
    ? res [0]
  : c == '('
    ? reverseInParentheses (cs, [...res, ''])
  : c == ')'
    ? reverseInParentheses (cs, [...res.slice(0, -2), res[res.length - 2] + [...res[res.length - 1]].reverse().join('')])
  : reverseInParentheses (cs, [...res.slice(0, -1), res[res.length - 1] + c])

console .log (reverseInParentheses('(bar)'))
console .log (reverseInParentheses('foo(bar)baz'))
console .log (reverseInParentheses('foo(bar(baz))blim'))
console .log (reverseInParentheses('((see)(you))'))

我们可以通过将此添加为正文表达式的第一行来检查行为：

  console .log (`c: ${c ? `"${c}"` : '< >'}, cs: "${cs.join('')}", res: ["${res.join('", "')}"]`) ||

对于'((see)(you))'，我们会得到这样的结果：

curr (`c`)	remaining (`cs`)	stack (`res`)
"("	"(see)(you))"	[""]
"("	"see)(you))"	["", ""]
"s"	"ee)(you))"	["", "", ""]
"e"	"e)(you))"	["", "", "s"]
"e"	")(you))"	["", "", "se"]
")"	"(you))"	["", "", "see"]
"("	"you))"	["", "ees"]
"y"	"ou))"	["", "ees", ""]
"o"	"u))"	["", "ees", "y"]
"u"	"))"	["", "ees", "yo"]
")"	")"	["", "ees", "you"]
")"	""	["", "eesuoy"]
< >	< >	["yousee"]

我选择递归地处理这个状态机，因为我更喜欢使用不可变数据，而不是重新分配变量等。但是这种技术应该同样适用于迭代方法。

Answer 2

String reverseInParentheses(String inputString) {
    //recursion
    int start = -1;
    int end = -1 ;
    for(int i = 0; i < inputString.length(); i++){
        if(inputString.charAt(i) == '('){
            start = i;
        }
        if(inputString.charAt(i) == ')'){
            end = i;
            String reverse = new StringBuilder(inputString.substring(start+1, end)).reverse().toString();
           return reverseInParentheses(inputString.substring(0, start) + reverse+ inputString.substring(end+1));
        }
    }
    return inputString;
}

CodeSignal reverseParentheses 失败一种情况

CodeSignal reverseParentheses Failing one case

javascript

string

algorithm

recursion

time-complexity

我的解决方案

问题