[39]寻找合法字符串-招商银行信用卡中心2018秋

1.题目描述

给出一个正整数 n，请给出所有的包含 n 个'('和 n 个')'的字符串，使得'('和')'可以完全匹配。

• 例如：
  '(())()'，'()()()' 都是合法的；
  '())()('是不合法的。

请按照字典序给出所有合法的字符串。

• 输入描述:
  输入为 1 个正整数
• 输出描述:
  输出为所有合法的字符串，用英文逗号隔开
• 输入示例：

  2
  

• 输出示例：

  (()),()()
  

2.题目解析

3.参考答案

方法一：
构造字符串，并且将字符串排列组合，过滤掉不匹配的情况，保留剩下的即为结果。

#include <bits/stdc++.h>
using namespace std;
bool check(string s){
    vector<char> stack;
    for(int i=0;i<s.size();++i){
        if(s[i] == '('){
            stack.push_back('(');
        }else if(s[i] == ')'){
            if(stack.empty()){// 如果前面没有做左括号，不匹配
                return false;
            }
            stack.pop_back();
        }
    }
    return stack.empty();
}
int main() {
  int n;
  scanf("%d",&n);
  string s = string(n,'(')+string(n,')');
  set<string> res;
  res.insert(s);
  do {
    if(check(s)){
      res.insert(s);
    }
  } while(next_permutation(s.begin(), s.end()));
  
  bool start = true;
  for(string str:res){
      if(start)start = false; // 除去开头，
      else cout <<',';
      cout << str ;
  }
  cout << '\n';
}

方法二：回溯法

回溯法的前提是熟练掌握和理解递归。

#include <bits/stdc++.h>
using namespace std;

void solve(int left, int right, string str, vector<string>& res){
    if (left == 0 && right == 0){
        res.push_back(str);
        return;
    }
    if (left>0) solve(left - 1, right, str + '(', res);
    if (right>left) solve(left, right - 1, str + ')', res);
}

int main(){
  int n;
  scanf("%d",&n);

  vector<string> res;
  solve(n,n,"",res);

  // 打印结果
  for(int i=0;i!=res.size();++i){
    cout << res[i];
    if(i!=res.size()-1){
        cout << ",";
    }
  }
  cout << endl;
  return 0;
}

解析

• 当n=2时

solve(2,2,"")
 solve(1,2,"(")
  solve(0,2,"((")
   solve(0,1,"(()")
    solve(0,0,"(())")
  solve(1,1,"()")
   solve(0,1,"()(")
    solve(0,0,"()()")

• 当n=3时

solve(3,3,"")
 solve(2,3,"(")
  solve(1,3,"((")
   solve(0,3,"(((")
    solve(0,2,"((()")
     solve(0,1,"((())")
      solve(0,0,"((()))")
   solve(1,2,"(()")
    solve(0,2,"(()(")
     solve(0,1,"(()()")
      solve(0,0,"(()())")
    solve(1,1,"(())")
     solve(0,1,"(())(")
      solve(0,0,"(())()")
  solve(2,2,"()")
   solve(1,2,"()(")
    solve(0,2,"()((")
     solve(0,1,"()(()")
      solve(0,0,"()(())")
    solve(1,1,"()()")
     solve(0,1,"()()(")
      solve(0,0,"()()()")

• 当n=4时

solve(4,4,"")
 solve(3,4,"(")
  solve(2,4,"((")
   solve(1,4,"(((")
    solve(0,4,"((((")
     solve(0,3,"(((()")
      solve(0,2,"(((())")
       solve(0,1,"(((()))")
        solve(0,0,"(((())))")
    solve(1,3,"((()")
     solve(0,3,"((()(")
      solve(0,2,"((()()")
       solve(0,1,"((()())")
        solve(0,0,"((()()))")
     solve(1,2,"((())")
      solve(0,2,"((())(")
       solve(0,1,"((())()")
        solve(0,0,"((())())")
      solve(1,1,"((()))")
       solve(0,1,"((()))(")
        solve(0,0,"((()))()")
   solve(2,3,"(()")
    solve(1,3,"(()(")
     solve(0,3,"(()((")
      solve(0,2,"(()(()")
       solve(0,1,"(()(())")
        solve(0,0,"(()(()))")
     solve(1,2,"(()()")
      solve(0,2,"(()()(")
       solve(0,1,"(()()()")
        solve(0,0,"(()()())")
      solve(1,1,"(()())")
       solve(0,1,"(()())(")
        solve(0,0,"(()())()")
    solve(2,2,"(())")
     solve(1,2,"(())(")
      solve(0,2,"(())((")
       solve(0,1,"(())(()")
        solve(0,0,"(())(())")
      solve(1,1,"(())()")
       solve(0,1,"(())()(")
        solve(0,0,"(())()()")
  solve(3,3,"()")
   solve(2,3,"()(")
    solve(1,3,"()((")
     solve(0,3,"()(((")
      solve(0,2,"()((()")
       solve(0,1,"()((())")
        solve(0,0,"()((()))")
     solve(1,2,"()(()")
      solve(0,2,"()(()(")
       solve(0,1,"()(()()")
        solve(0,0,"()(()())")
      solve(1,1,"()(())")
       solve(0,1,"()(())(")
        solve(0,0,"()(())()")
    solve(2,2,"()()")
     solve(1,2,"()()(")
      solve(0,2,"()()((")
       solve(0,1,"()()(()")
        solve(0,0,"()()(())")
      solve(1,1,"()()()")
       solve(0,1,"()()()(")
        solve(0,0,"()()()()")

牛客题目