Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1190.html
1190. Reverse Substrings Between Each Pair of Parentheses (Medium)
Given a string s that consists of lower case English letters and brackets.
Reverse the strings in each pair of matching parentheses, starting from the innermost one.
Your result should not contain any bracket.
Example 1:
Input: s = "(abcd)" Output: "dcba"
Example 2:
Input: s = "(u(love)i)" Output: "iloveu"
Example 3:
Input: s = "(ed(et(oc))el)" Output: "leetcode"
Example 4:
Input: s = "a(bcdefghijkl(mno)p)q" Output: "apmnolkjihgfedcbq"
Constraints:
0 <= s.length <= 2000sonly contains lower case English characters and parentheses.- It's guaranteed that all parentheses are balanced.
Companies:
Adobe
Related Topics:
Stack
Solution 1. Recursive
We scan through the string. Once we see (, we go one layer deeper. Each layer returns once it see a ) or end of string.
// OJ: https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
private:
string solve(string &s, int &i) {
string ans;
int N = s.size();
while (i < N) {
while (i < N && s[i] != '(' && s[i] != ')') ans += s[i++];
if (i < N) ++i;
if (i >= N || s[i - 1] == ')') break;
auto mid = solve(s, i);
reverse(mid.begin(), mid.end());
ans += mid;
}
return ans;
}
public:
string reverseParentheses(string s) {
int i = 0;
return solve(s, i);
}
};
Solution 2.
There is a pattern in the reversed string. For each pair of parenthesis, when we see '(' or ')', we jump to the corresponding ')' or '(' and toggle the direction we scan.
Example:
1 2 3 4
v v v v
a ( b ( cd ) e ) f
- We scan rightwards initially.
ans = a - When we meet the parenthesis
1from left to right, we jump to its corresponding parenthesis4and toggle the direction to be leftwards.ans = ae - When we meet the parenthesis
3from right to left, we jump to its corresponding parenthesis2and toggle direction to be rightwards.ans = aecd - When we meet the parenthesis
3from left to right, we jump to2and toggle direction to be leftwards.ans = aecdb. - When we meet the parenthesis
1from right to left, we jump to4and toggle direction to be rightwards.ans = aecdbf. - We’ve reached the end. The answer is
aecdbf.
// OJ: https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/
// Time: O(N)
// Space: O(P) where P is the number of pairs of parenthesis in `s`.
// Ref: https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/discuss/383670/JavaC%2B%2BPython-Why-not-O(N)
class Solution {
public:
string reverseParentheses(string s) {
stack<int> st;
unordered_map<int, int> m;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') st.push(i);
else if (s[i] == ')') {
m[i] = st.top();
m[st.top()] = i;
st.pop();
}
}
string ans;
for (int i = 0, d = 1; i < s.size(); i += d) {
if (s[i] == '(' || s[i] == ')') {
i = m[i];
d = -d;
} else ans += s[i];
}
return ans;
}
};
-
class Solution { public String reverseParentheses(String s) { Stack<Character> stack = new Stack<Character>(); int length = s.length(); for (int i = 0; i < length; i++) { char c = s.charAt(i); if (c != ')') stack.push(c); else { Queue<Character> queue = new LinkedList<Character>(); while (!stack.isEmpty() && stack.peek() != '(') queue.offer(stack.pop()); stack.pop(); while (!queue.isEmpty()) stack.push(queue.poll()); } } StringBuffer sb = new StringBuffer(); while (!stack.isEmpty()) sb.append(stack.pop()); sb.reverse(); return sb.toString(); } } ############ class Solution { public String reverseParentheses(String s) { int n = s.length(); int[] d = new int[n]; Deque<Integer> stk = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { if (s.charAt(i) == '(') { stk.push(i); } else if (s.charAt(i) == ')') { int j = stk.pop(); d[i] = j; d[j] = i; } } StringBuilder ans = new StringBuilder(); int i = 0, x = 1; while (i < n) { if (s.charAt(i) == '(' || s.charAt(i) == ')') { i = d[i]; x = -x; } else { ans.append(s.charAt(i)); } i += x; } return ans.toString(); } } -
// OJ: https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/ // Time: O(N^2) // Space: O(N^2) class Solution { private: string solve(string &s, int &i) { string ans; int N = s.size(); while (i < N) { while (i < N && s[i] != '(' && s[i] != ')') ans += s[i++]; if (i < N) ++i; if (i >= N || s[i - 1] == ')') break; auto mid = solve(s, i); reverse(mid.begin(), mid.end()); ans += mid; } return ans; } public: string reverseParentheses(string s) { int i = 0; return solve(s, i); } }; -
class Solution: def reverseParentheses(self, s: str) -> str: n = len(s) d = [0] * n stk = [] for i, c in enumerate(s): if c == '(': stk.append(i) elif c == ')': j = stk.pop() d[i], d[j] = j, i i, x = 0, 1 ans = [] while i < n: if s[i] in '()': i = d[i] x = -x else: ans.append(s[i]) i += x return ''.join(ans) ############ # 1190. Reverse Substrings Between Each Pair of Parentheses # https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/ class Solution: def reverseParentheses(self, s: str) -> str: stack = [] for c in s: if c == "(": stack.append([]) elif c == ")": words = stack.pop()[::-1] if stack: stack[-1] += words else: stack.append(words) else: if stack: stack[-1].append(c) else: stack.append([c]) return "".join(stack[-1]) -
func reverseParentheses(s string) string { n := len(s) d := make([]int, n) stk := []int{} for i, c := range s { if c == '(' { stk = append(stk, i) } else if c == ')' { j := stk[len(stk)-1] stk = stk[:len(stk)-1] d[i], d[j] = j, i } } ans := []byte{} i, x := 0, 1 for i < n { if s[i] == '(' || s[i] == ')' { i = d[i] x = -x } else { ans = append(ans, s[i]) } i += x } return string(ans) } -
/** * @param {string} s * @return {string} */ var reverseParentheses = function (s) { const n = s.length; const d = new Array(n).fill(0); const stk = []; for (let i = 0; i < n; ++i) { if (s[i] == '(') { stk.push(i); } else if (s[i] == ')') { const j = stk.pop(); d[i] = j; d[j] = i; } } let i = 0; let x = 1; const ans = []; while (i < n) { const c = s.charAt(i); if (c == '(' || c == ')') { i = d[i]; x = -x; } else { ans.push(c); } i += x; } return ans.join(''); };