'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:
- s:
a(bcdefghijkl(mno)p)qExpected Output:apmnolkjihgfedcbq - s:
co(de(fight)s)Expected Output:cosfighted
Solution 1:[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)
}
Solution 2:[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;
}
Solution 3:[3]
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
Solution 4:[4]
Here is a solution:
const reverse = (str) => str.split('').reverse().join('');
const 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;
};
Solution 5:[5]
Here is a modified version of Vahan's answer, condensing the regex execution into only one replace call:
function reverseInParentheses(inputString) {
regex = /\(([^()]*)\)/i;
if (inputString.includes('(')) {
return reverseInParentheses(inputString.replace(regex, (_, $1) => $1.split('').reverse().join('')));
} else {
return inputString
}
}
Solution 6:[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;
}
Solution 7:[7]
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;
}Solution 8:[8]
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);
}
Solution 9:[9]
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
Solution 10:[10]
def reverseParentheses(s)
0 while s.gsub!(/\(([^()]*)\)/) { $1.reverse }
return s
end
Solution 11:[11]
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
Solution 12:[12]
In Java: Simple Method
String reverseInParentheses(String inputString) {
StringBuilder str = new StringBuilder();
int start = 0;
int end = inputString.length() - 1;
str.setLength(0);
if (inputString.contains("(")) {
start = inputString.lastIndexOf("(");
end = inputString.indexOf(")", start);
str.append(inputString, start+1, end);
return reverseInParentheses(inputString.substring(0, start) + str.reverse().toString() + inputString.substring(end+1));
}
return inputString;
}
Solution 13:[13]
In Javascript
function reverseInParentheses(inputString) {
let mainArr = inputString.split('');
let arrLength = mainArr.length;
let arr1 = [];
for(let i = 0; i < arrLength; i++) {
if(mainArr[i] != ')') {
arr1.push(mainArr[i]);
} else {
let temp = reverseSelectedString(arr1); // call function to reverse selected string
arr1 = arr1.splice(0, arr1.lastIndexOf("("));
arr1 = arr1.concat(temp);
}
}
return arr1.join('');
}
function reverseSelectedString(arrFirst) {
let arr2 = [];
let arrLength = arrFirst.length;
for(let j = arrLength; j >= 0; j--) {
if(arrFirst[j] != '(') {
arr2.push(arrFirst[j]);
} else {
break;
}
}
return arr2;
}
Solution 14:[14]
In Javascript/node js
//Regex for opening and closing parenthesis
const o_brc = /[\{\[\(]/g;
const c_brc= /[\}\]\)]/g;
const revPar = str => {
let top =-1;
let rev_str = [];
for(let i in str){
if(c_brc.test(str[i])){
const rev = [];
let j = i-1;
while(rev_str.length){
if(o_brc.test(rev_str[top])){
break;
}
rev.push( rev_str.pop());
top--;
}
rev_str.pop(); //pop out the opening brackets after reversing
top--;
rev_str = [...rev_str, ...rev];
top += rev.length; //increment the top upto rev.length
}
else{
rev_str.push(str[i]); //push to rev_str if not a closing bracket
top++;
}
}
console.log((rev_str.join('')));
}
Solution 15:[15]
this is a nice straight forward answer in c++
whenever we see open parentheses we push the index into the stack, and when we find a closing one, we pop the last index and reverse the substring between those two indises. then we remove the additional parentheses
string reverseInParentheses(string inputString) {
stack<int> index;
for (int i = 0 ; i < inputString.length(); i++){
if (inputString[i] == '('){
index.push(i);
}
if (inputString[i] == ')'){
reverse(inputString.begin()+ index.top(), inputString.begin()+i+1);
index.pop();
}
}
string s = "";
for (int i = 0; i < inputString.length();i++){
if (inputString[i] != '(' && inputString[i] != ')' )
s += inputString[i];
}
cout << s << endl;
return s;
}
Solution 16:[16]
My approach is to find the pairing parentheses, reverse the sequence in the parenthesis. At the end, use filter() to remove all the parentheses. The solution is a little bit wordy compare to other solutions, but I find that I can follow up this approach better.
function reverseInParentheses(inputString) {
const stack = [];
let inputList = inputString.split("");
for (let i = 0; i < inputList.length; i++) {
if (inputList[i] === "(") {
stack.push(i);
} else if (inputList[i] === ")") {
const begin = stack.pop();
const reversedSeq = reverseString(inputList.slice(begin + 1, i));
appendSubsequence(reversedSeq, inputList, begin + 1);
}
}
return inputList.filter((char) => char !== "(" && char !== ")").join("");
}
const reverseString = (sequence) => {
for (let i = 0; i < sequence.length / 2; i++) {
const endIndex = sequence.length - i - 1;
[sequence[i], sequence[endIndex]] = [sequence[endIndex], sequence[i]];
}
return sequence;
};
const appendSubsequence = (sequence, arr, begin) => {
let counter = 0;
while (counter < sequence.length) {
arr[begin++] = sequence[counter++];
}
};
Solution 17:[17]
Simple and easy with DEQUEUE
String reverseInParentheses(String s) {
Deque dq = new LinkedList<Character>();
for(int i=0;i<s.length();i++){
dq.add(s.charAt(i));
if(s.charAt(i)==')'){
int k=i-1;
String temp="";
dq.removeLast();
char c1=(char)dq.getLast();
while(c1!='('){
temp=temp+dq.removeLast().toString();
c1=(char)dq.getLast();
}
dq.removeLast();
int c=0;
while(c<temp.length()){
dq.add(temp.charAt(c));
c++;
}
}
}
String temp="";
Iterator iteratorVals = dq.iterator();
while (iteratorVals.hasNext()) {
temp=temp+iteratorVals.next();
}
return temp;
}
Solution 18:[18]
i couldnt understand the python top solution so I had to break it in chunks to understand.
In Python:
Simple Method
def reverseInParentheses(s):
return eval('"' + s.replace('(', '"+("').replace(')', '")[::-1]+"') + '"')
s = "abc(def(ghi)klm)nop"
print("original",s)
print("first replace", s.replace('(', '"+("'))
print("second replace", s.replace('(', '"+("').replace(')', '")[::-1]+"'))
print("third step addition",'"' + s.replace('(', '"+("').replace(')', '")[::-1]+"') + '"')
print('final evaluation', eval('"' + s.replace('(', '"+("').replace(')', '")[::-1]+"') + '"'))
output:
original abc(def(ghi)klm)nop
first replace abc"+("def"+("ghi)klm)nop
second replace abc"+("def"+("ghi")[::-1]+"klm")[::-1]+"nop
third step addition "abc"+("def"+("ghi")[::-1]+"klm")[::-1]+"nop"
final abcmlkghifednop
Solution 19:[19]
Here is my solution that passed:
function extractParenthesesAndKey(input) {
const match = input.match(/\(([^()]*)\)/i);
if (!match) return null;
const result = match[0];
const key = result.substring(1, result.length - 1);
return { result, key };
}
function hasParentheses(string) {
return string.includes('(') || string.includes(')');
}
function solution(inputString) {
let interpolatedInput = inputString.slice(); // no side-effect
let itHasParentheses = hasParentheses(interpolatedInput);
while(itHasParentheses) {
const extractedData = extractParenthesesAndKey(interpolatedInput);
interpolatedInput = interpolatedInput.replace(extractedData.result,
extractedData.key
.split('')
.reverse()
.join(''));
solution(interpolatedInput);
itHasParentheses = hasParentheses(interpolatedInput);
}
return interpolatedInput;
}
Solution 20:[20]
function solution(inputString) {
while(inputString.includes('(')){
inputString = inputString.replaceAll(/\([a-z]*\)/g, str=>str.split('').slice(1, -1).reverse().join(''));
}
return inputString
}
Have found this solution much clear and ease
Solution 21:[21]
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();
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow