【LetMeFly】1190.反转每对括号间的子串递归 / 指针横跳力扣题目链接https://leetcode.cn/problems/reverse-substrings-between-each-pair-of-parentheses/给出一个字符串s仅含有小写英文字母和括号。请你按照从括号内到外的顺序逐层反转每对匹配括号中的字符串并返回最终的结果。注意您的结果中不应包含任何括号。示例 1输入s (abcd)输出dcba示例 2输入s (u(love)i)输出iloveu解释先反转子字符串 love 然后反转整个字符串。示例 3输入s (ed(et(oc))el)输出leetcode解释先反转子字符串 oc 接着反转 etco 然后反转整个字符串。提示1 s.length 2000s中只有小写英文字母和括号题目测试用例确保所有括号都是成对出现的解题方法一递归写一个dfs函数遍历传入的字符串遇到字母则直接拼接到答案中遇到左括号则找到对应的右括号然后递归middle dfs(该括号中的子串)把middle反转后拼接到答案中。直到遍历完整个字符串为止。时间复杂度O ( l e n ( s ) 2 ) O(len(s)^2)O(len(s)2)空间复杂度O ( l e n ( s ) ) O(len(s))O(len(s))AC代码C/* * LastEditTime: 2026-09-27 08:49:50 *//* (ed(et(oc))el) [ed ] [ed te] [ed oc te] [ed oc le te] 两栈不可 */classSolution{private:size_tfind_end(string_view s,size_t left){size_t idxleft1;for(size_t layer1;layer;idx){if(s[idx](){layer;}elseif(s[idx])){layer--;}}return--idx;}stringdfs(string_view s){string ans;for(size_t i0,ns.size();in;i){if(s[i](){size_t endfind_end(s,i);string resdfs(s.substr(i1,end-i-1));reverse(res.begin(),res.end());ansres;iend;}else{anss[i];}}returnans;}public:stringreverseParentheses(conststrings){returndfs(s);}};解题方法二指针横跳按照题目意思模拟。使用一个指针从左到右遍历字符串遇到左括号则跳转到对应的右括号的位置向左遍历遇到右括号则跳转到对应的左括号的位置向右遍历。遇到字母则直接拼接到答案中。我们可以预处理得到每个括号与之配对的括号的位置。创建一个m a t e matemate数组m a t e [ i ] mate[i]mate[i]表示与下标为i ii的括号匹配的括号的下标。使用一个栈遍历字符串遇到左括号则将其下标入栈遇到右括号则将栈顶的下标出栈即说明二者是一对。时间复杂度O ( l e n ( s ) ) O(len(s))O(len(s))空间复杂度O ( l e n ( s ) ) O(len(s))O(len(s))该算法暂未规范名称暂时归类到双指针标签下。AC代码C/* * LastEditTime: 2026-09-27 09:12:03 */classSolution{public:stringreverseParentheses(conststrings){intns.size();vectorintmate(n);stackintst;for(inti0;in;i){if(s[i](){st.push(i);}elseif(s[i])){intgirlfriendst.top();st.pop();mate[girlfriend]i;mate[i]girlfriend;}}string ans;ans.reserve(n);for(inti0,direction1;in;idirection){if(s[i](||s[i])){imate[i];direction-direction;}else{anss[i];}}returnans;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源
LeetCode 1190.反转每对括号间的子串：递归 / 指针横跳
【LetMeFly】1190.反转每对括号间的子串递归 / 指针横跳力扣题目链接https://leetcode.cn/problems/reverse-substrings-between-each-pair-of-parentheses/给出一个字符串s仅含有小写英文字母和括号。请你按照从括号内到外的顺序逐层反转每对匹配括号中的字符串并返回最终的结果。注意您的结果中不应包含任何括号。示例 1输入s (abcd)输出dcba示例 2输入s (u(love)i)输出iloveu解释先反转子字符串 love 然后反转整个字符串。示例 3输入s (ed(et(oc))el)输出leetcode解释先反转子字符串 oc 接着反转 etco 然后反转整个字符串。提示1 s.length 2000s中只有小写英文字母和括号题目测试用例确保所有括号都是成对出现的解题方法一递归写一个dfs函数遍历传入的字符串遇到字母则直接拼接到答案中遇到左括号则找到对应的右括号然后递归middle dfs(该括号中的子串)把middle反转后拼接到答案中。直到遍历完整个字符串为止。时间复杂度O ( l e n ( s ) 2 ) O(len(s)^2)O(len(s)2)空间复杂度O ( l e n ( s ) ) O(len(s))O(len(s))AC代码C/* * LastEditTime: 2026-09-27 08:49:50 *//* (ed(et(oc))el) [ed ] [ed te] [ed oc te] [ed oc le te] 两栈不可 */classSolution{private:size_tfind_end(string_view s,size_t left){size_t idxleft1;for(size_t layer1;layer;idx){if(s[idx](){layer;}elseif(s[idx])){layer--;}}return--idx;}stringdfs(string_view s){string ans;for(size_t i0,ns.size();in;i){if(s[i](){size_t endfind_end(s,i);string resdfs(s.substr(i1,end-i-1));reverse(res.begin(),res.end());ansres;iend;}else{anss[i];}}returnans;}public:stringreverseParentheses(conststrings){returndfs(s);}};解题方法二指针横跳按照题目意思模拟。使用一个指针从左到右遍历字符串遇到左括号则跳转到对应的右括号的位置向左遍历遇到右括号则跳转到对应的左括号的位置向右遍历。遇到字母则直接拼接到答案中。我们可以预处理得到每个括号与之配对的括号的位置。创建一个m a t e matemate数组m a t e [ i ] mate[i]mate[i]表示与下标为i ii的括号匹配的括号的下标。使用一个栈遍历字符串遇到左括号则将其下标入栈遇到右括号则将栈顶的下标出栈即说明二者是一对。时间复杂度O ( l e n ( s ) ) O(len(s))O(len(s))空间复杂度O ( l e n ( s ) ) O(len(s))O(len(s))该算法暂未规范名称暂时归类到双指针标签下。AC代码C/* * LastEditTime: 2026-09-27 09:12:03 */classSolution{public:stringreverseParentheses(conststrings){intns.size();vectorintmate(n);stackintst;for(inti0;in;i){if(s[i](){st.push(i);}elseif(s[i])){intgirlfriendst.top();st.pop();mate[girlfriend]i;mate[i]girlfriend;}}string ans;ans.reserve(n);for(inti0,direction1;in;idirection){if(s[i](||s[i])){imate[i];direction-direction;}else{anss[i];}}returnans;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源
