[1190] 反转每对括号间的子串

[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"

提示：

• 0 <= s.length <= 2000
• s 中只有小写英文字母和括号
• 我们确保所有括号都是成对出现的

• 思路

• 依次遍历字符串，找到所有最外层括号后反转数组,由于是遍历数组，反转过程中不能先去除括号，应该保证括号状态不反转（即反转后右括号肯定在左边，改回左括号），并递归检查该括号内是否还有括号，直到没有括号。

  代码

class Solution {
public:
    void reverseHelper(string &s,int being_index,int end_index)
 {
	 int left =being_index;
	 int index = 0;
	 for(int i = being_index; i < end_index; ++i)
	 {
		 if(s[i] == '(')
		 {
			 if(index == 0) left = i;
			 index ++;
		 }
		 if(s[i] == ')')
		 {
			 index --;
			 if(index == 0)
			 {
				 int tmp_left = left;
				 int tmp_right = i;
				 while(tmp_left < tmp_right)
				 {
					 char tmp = s[tmp_left];
					 s[tmp_left] = s[tmp_right];
					 s[tmp_right] = tmp;
					 if(s[tmp_left] == '(' || s[tmp_left] == ')')
					 {
						 s[tmp_left] = s[tmp_left] == '(' ? ')' : '(';
					 }
					 if(s[tmp_right] == '(' || s[tmp_right] == ')')
					 {
						 s[tmp_right] = s[tmp_right] == '(' ? ')' : '(';
					 }
					 tmp_left ++;
					 tmp_right --;
				 }
				 if(tmp_left == tmp_right &&( s[tmp_left] == '(' || s[tmp_left] == ')'))
				 {
					s[tmp_left] = s[tmp_left] == '(' ? ')' : '(';
				 }
				 reverseHelper(s,left + 1,i);
			 }
		 }
	 }
 }

 string reverseParentheses(string s) {

	 reverseHelper(s,0,(int)s.size());
	 string tmp;
	 for(int i = 0; i < (int)s.size(); ++i)
	 {
		 if(s[i] != '(' && s[i] != ')')
		 {
			 tmp.push_back(s[i]);
		 }
	 }

	 s = tmp;
	 return s;
 }
};
​