LeetCode Entry
1190. Reverse Substrings Between Each Pair of Parentheses
Reverse string in parentheses recursively
1190. Reverse Substrings Between Each Pair of Parentheses medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/666
Problem TLDR
Reverse string in parentheses recursively #medium
Intuition
The simplest way is to simulate the reversing: do Depth-First Search and use parenthesis as nodes. It will take O(n^2) time.
There is also an O(n) solution possible.
Approach
- let’s use LinkedList in Rust, it will make solution O(n)
Complexity
-
Time complexity: \(O(n^2)\), O(n) for the Linked List solution
-
Space complexity: \(O(n)\)
Code
fun reverseParentheses(s: String): String {
var i = 0
fun dfs(): String = buildString {
while (i < s.length)
if (s[i] == '(') {
i++
append(dfs().reversed())
i++
} else if (s[i] == ')') break
else append(s[i++])
}
return dfs()
}
pub fn reverse_parentheses(s: String) -> String {
fn dfs(chars: &mut Chars, rev: bool) -> LinkedList<char> {
let mut list = LinkedList::<char>::new();
while let Some(c) = chars.next() {
if c == ')' { break }
if c == '(' {
let mut next = dfs(chars, !rev);
if rev { next.append(&mut list); list = next }
else { list.append(&mut next) }
} else { if rev { list.push_front(c) } else { list.push_back(c) }}
}; list
}
return dfs(&mut s.chars(), false).into_iter().collect()
}