1190 反转每对括号间的子串
问题描述:
给出一个字符串 s(仅含有小写英文字母和括号)。
请你按照从括号内到外的顺序,逐层反转每对匹配括号中的字符串,并返回最终的结果。
注意,您的结果中不应包含任何括号。
示例1:
输入:s = "(abcd)"
输出:"dcba"
示例2:
输入:s = "(u(love)i)"
输出:"iloveu"
示例3:
输入:s = "(ed(et(oc))el)"
输出:"leetcode"
示例4:
输入:s = "a(bcdefghijkl(mno)p)q"
输出:"apmnolkjihgfedcbq"
思路:
【暴力】
这个反转很明显需要用到栈的思维,我们就暴力的按照题目描述,遇到括号就将其反转即可。
- 定义一个队列,一个栈,遇到右括号,我们在栈中找左括号
- 将中间的元素全部放到队列中
- 再将队列中的所有元素压入栈中,这样就做到了将其反转的操作
- 遍历所有这样的元素
- 最后我们返回栈中的元素即可
Java代码:
/**
* @Description: 力扣1190题题解
* @return: 返回结果
* @Author: Mr.Gao
* @Date: 2021/5/26
*/
public String reverseParentheses(String s) {
Stack<Character> stack1 = new Stack<>();
Queue<Character> stack2 = new LinkedList<>();
int n = s.length();
for (int i = 0; i < n; i++) {
if(s.charAt(i)!=')'){
stack1.push(s.charAt(i));
}else{
while(stack1.peek()!='('){
stack2.add(stack1.pop());
}
stack1.pop();
while(!stack2.isEmpty()){
stack1.push(stack2.poll());
}
}
}
String re = "";
while (!stack1.empty()) {
re = stack1.pop()+re;
}
return re;
}