ReverseParentheses - Codefights

问题:

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"

回答1:

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)
}

回答2:

def reverseParentheses(s):
    for i in range(len(s)):
        if s[i] == "(":
            start = i
            print (s[:start])
        if s[i] == ")":
            end = i
            print (end)
            return reverseParentheses(s[:start] + s[start+1:end][::-1] + s[end+1:])
    return s

回答3:

Here is a solution:

var reverse = (str) => str.split('').reverse().join('');

var reverseParentheses = (s) => {
    while (s.includes('(')) {
        var l = s.lastIndexOf('(');
        var r = s.indexOf(')', s.lastIndexOf('('));
        s = s.slice(0, l) + reverse(s.slice(l + 1, r)) + (r + 1 === s.length ? s.slice(r, -1) : s.slice(r + 1));
    }
    return s;
};

回答4:

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;
}

回答5:

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;
}

回答6:

Here's my JS solution without using regular expressions, it might be more understandable for a beginner. The comments make the code self-explanatory but the idea is to find the last opening bracket (in case the expression has nested brackets), and then find the matching closing bracket, reverse the text inside and keep running the function until the string doesn't have any more opening brackets (and by the definition of the problem, no more closing brackets).

function reverseParentheses(s) {
    // We keep running the function while 
    // there's an opening bracket in the string
    while (s.indexOf("(") !== -1) {
        s = reverseP(s);
    }
    return s;
}

function reverseP(s) {
    let len = s.length;
    // We find the innermost/last opening bracket,
    // and then we're going to find the matching closing bracket,
    // which is the next closing bracket after the opening bracket
    let openBracketInd = s.lastIndexOf("(");
    
    // The characters before the opening bracket
    let beforeBracket = s.slice(0, openBracketInd+1);
    
    // The characters before the opening bracket
    let afterBracket = s.slice(openBracketInd+1, len);
    
    // To get the index of the closing bracket we add the 
    // characters before the bracket to the index of the first closing
    // bracket in the string after the opening bracket
    let closeBracketInd = beforeBracket.length + afterBracket.indexOf(")");
    
    // Once we have the indexes, we're going to slice the string 
    // to remove the brackets
    let firstPart = s.slice(0, openBracketInd);
    let secondPart = s.slice(closeBracketInd+1, len);
    let middle = s.slice(openBracketInd+1, closeBracketInd);
    
    // We reverse the string between the brackets
    middle = middle.split('').reverse().join('');
    
    // And finally we join the parts and return the string
    return firstPart+middle+secondPart;
}

回答7:

This is a recursive solution using regular expressions, there is a reverseString method that get called when there is a match in the regular expression, this match uses the replace function in order to replace the reveresed string. once is reversed it does the cycle again until there are no more matches..

function reverseParentheses(s) {
    const reverseString = str => (str === '') ? '' : reverseString(str.substr(1)) + str.charAt(0);
    const regex = /(\([\w\s\[\]!\.\,\;\:\?]*\))/g;
    const iterator = a => {
        if(regex.test(a)){
            a=a.replace(regex, full => reverseString(full.replace(/[()]/g,'')));    
            return iterator(a);
        } else  return a;
    }
    return iterator(s);   
}

回答8:

For Python 3 (not sure about Python 2), this code works. This does assume (as the problem on Code Fights states) that each parenthesis is a part of a pair.

def reverseParentheses(s):
    from collections import Counter
    for i in range(Counter(s)['(']):
        one = s.rsplit('(',1)
        two = one[1].split(')',1)
        s = one[0]+two[0].replace(two[0],two[0][::-1]+two[1])
        print(s)
    return s 

回答9:

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

回答10:

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

回答11:

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();
}