ReverseParentheses - Codefights

Question

I'm having a really tough time solving this problem with JavaScript

You are given a string s that consists of English letters, punctuation marks, whitespace characters and brackets. It is guaranteed that the brackets in s form a regular bracket sequence.

Your task is to reverse the strings in each pair of matching parenthesis, starting from the innermost one.

Example

For string "s = a(bc)de" the output should be

reverseParentheses(s) = "acbde".

Input/Output

[time limit] 4000ms (js) [input] string s

A string consisting of English letters, punctuation marks, whitespace characters and brackets. It is guaranteed that parenthesis form a regular bracket sequence.

Constraints:

5 ≤ x.length ≤ 55.

[output] string

It has to work with the following inputs:

1. s: "a(bcdefghijkl(mno)p)q" Expected Output: "apmnolkjihgfedcbq"
2. s: "co(de(fight)s)" Expected Output: "cosfighted"

Answer 1

def reverseParentheses(s)
  0 while s.gsub!(/\(([^()]*)\)/) { $1.reverse }
  return s
end

Answer 2

In JS

Using Regex

function reverseInParentheses(s) {
    if (s.match(/\([a-z]*\)/)) {
        return reverseInParentheses(s.replace(/\([a-z]*\)/, 
            Array.from(s.match(/\([a-z]*\)/)[0].replace(/\(|\)/g,'')).reverse().join('')));
    }
    else return s;
}

Simple Method:-

function reverseInParentheses(s) {
    while (true) {
        let c = s.indexOf(")");    
        if (c === -1) break;
        let o = s.substring(0, c).lastIndexOf("(");
        let start = s.substring(0, o);
        let middle = s.substring(o + 1, c).split("").reverse().join("");
        let end = s.substring(c + 1, s.length);
        s = start + middle + end;
    }
    return s;
}

In Python:

Simple Method

def reverseInParentheses(s):
    return eval('"' + s.replace('(', '"+("').replace(')', '")[::-1]+"') + '"')

Using Stacks Method

def reverseInParentheses(s):
    stack = []
    for x in s:
        if x == ")":
            tmp = ""
            while stack[-1] != "(":
                tmp += stack.pop()
            stack.pop() # pop the (
            for item in tmp:
                stack.append(item)
        else:
            stack.append(x)

    return "".join(stack)

In C++

Simple Method:-

reverseString function will reverse the String using the swapping method while reverseParentheses function will update string recursively.

string reverseString(string s){
    for(int i = 0;i < s.length()/2;i++){
        char t = s[s.length()-1-i];
        s[s.length()-1-i] = s[i];
        s[i] = t;
    }
    return s;
}
string reverseInParentheses(string s) {
    int beg = 0;
    int end = s.length() - 1;
    for(int i = 0; i < s.length(); i++){
        if(s[i] == '(')
            beg = i;
        if(s[i] == ')'){
            end = i;
            string temp = s.substr(beg + 1, end - beg - 1);
            return reverseInParentheses(s.substr(0, beg) + reverseString(temp) + s.substr(end + 1));
         }
    }
    return s;
}

Answer 3

public static String reverseParentheses(String s) {
    StringBuilder sb = new StringBuilder();
    char[] sArray = s.toCharArray();
    int[] firstIndex = new int[s.length()]; //所有'('的索引
    int[] lastIndex = new int[s.length()]; //所有')'的索引
    int num = 0; // 表示遇到')'括号的次数
    int count = 0; // 表示遇到"("括号的次数
    boolean flag = false; //多种情况的判断
    int index; //')'对应'('的位置
    int countParentheses; //')'对应的'('的前面的括号个数
    for (int i = 0; i < sArray.length; i++) {
        if (sArray[i] == '(') {
            //第一种情况
            if (count == num && count != 0) {
                flag = true;
            } else if (count - num > 1 && num != 0) {//第三种情况
                flag = true;
            }
            firstIndex[count] = i;
            count++;
            continue;

        } else if (sArray[i] == ')') {
            System.out.println("开始->遇到')'：" + sb);
            lastIndex[num] = i;
            if (flag) {
                index = count - num;
                countParentheses = count + num;
                flag = false;
            } else {
                //第二种情况
                index = count - num - 1;
                countParentheses = count - num;

            }
            System.out.println("截取初始位置:" + (firstIndex[index] - (countParentheses) + 1));
            String s1 = sb.substring(firstIndex[index] - (countParentheses) + 1, lastIndex[num] - num - count);
            System.out.println("截取出括号内的字符串：" + s1);
            StringBuilder getString = new StringBuilder();
            getString.append(s1);
            getString.reverse();//反转
            System.out.println("替代起始位置：" + (firstIndex[index] - (countParentheses) + 1));
            System.out.println("替代的末位置:" + (lastIndex[num] - count - num));
            System.out.println("字符串长度：" + getString.toString().length());
            sb.replace(firstIndex[index] - (countParentheses) + 1, lastIndex[num] - count - num,
                    getString.toString().trim());
            System.out.println("反转后：" + sb);
            num++;
            continue;

        } else if (sArray[i] == ')' && count == num) {

        } else {
            sb.append(sArray[i]);
        }
    }

    System.out.println("...." + sb);
    return sb.toString();
}

Answer 4

function reverseParentheses(s) {
    if (s.includes('(')){
        return reverseParentheses(reverseOnce(s));
    } else {     
        return s;
    }
}

function reverseOnce(s){
    var regexp = /\(([^()]*)\)/i;
    var subStr = regexp.exec(s)[1];
    subStr = subStr.split('').reverse().join('');
    return s.replace(regexp, subStr)
}

Answer 5

A solution in F#:

let foldi fold first source =
    source
    |> List.fold (fun (prev,i) c -> (fold i prev c,i + 1)) (first,0)
    |> fst

let reverseParentheses (s: string) =
    let go pos (stack: list<list<char>>) (c: char) : list<list<char>> =
        let fail () = failwithf "Parse error at pos %d, char '%c'." pos c
        match c with
        | '(' -> [] :: stack
        | ')' ->
            match stack with
            | top :: next :: rest -> ((List.rev top @ next) :: rest)
            | _ -> fail ()
        | _ ->
            match stack with
            | top :: rest -> ((c :: top) :: rest)
            | _ -> fail ()
    s |> Seq.toList |> foldi go [[]] |> List.head |> List.rev |> List.toArray |> String

Answer 6

Given a string of size n, here's a recursion code written in C which runs in O(n) time complexity. The idea behind the code is to start with the beginning of the string and every time you encounter an opening bracket, you switch to its closing bracket and print backwards then complete printing after that closing brackets. Note that when you are printing backwards, opening brackets '[' are considered closing brackets and vise versa for closing brackets ']'. Maximum string size is 1 million, change array sizes if you need to process longer strings.

#include <stdio.h>
#include <string.h>
int n, other[1000010], stt[1000010];
char st[1000010];

void rec(int i, int dir) {
    if(i >= n) return;
    if(st[i] == '[') {
        if(dir == 1) { // going right with '[' means opening
            rec(other[i]-1, -dir); // go to the closing bracket and change direction
            rec(other[i]+1, dir); // continue after the closing bracket after finishing
        }
        return;
    }

    if(st[i] == ']') {
        if(dir == -1) { // going left with ']' means opening
            rec(other[i]+1, -dir); // go to the closing bracket and change direction
            rec(other[i]-1, dir); // continue after the closing bracket after finishing
        }
        return;
    }
    putchar(st[i]); // print character
    rec(i+dir, dir); // continue same direction
}

int main() {
    scanf("%s", st);
    n = strlen(st);
    for(int i=0, j, k=0; i<n; ++i) {
        if(st[i] == '[') stt[k++] = i;
        else if(st[i] == ']')  {
            j = stt[--k];
            other[i] = j, other[j] = i;
        }
    }
    rec(0, 1); // start from 0, with direction 1 (right)
    return 0;
}