首页 > 试题广场 >

寻找合法字符串

[编程题]寻找合法字符串
  • 热度指数:1018 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给出一个正整数n,请给出所有的包含n个'('和n个')'的字符串,使得'('和')'可以完全匹配。
例如:
'(())()','()()()' 都是合法的;
'())()('是不合法的。
请按照__字典序__给出所有合法的字符串。

输入描述:
输入为1个正整数


输出描述:
输出为所有合法的字符串,用英文逗号隔开
示例1

输入

2

输出

(()),()()
/**
 * 寻找合法字符串
 * 给出一个正整数n,请给出所有的包含n个'('和n个')'的字符串,使得'('和')'可以完全匹配。
 * 例如:
 * '(())()','()()()' 都是合法的;
 * '())()('是不合法的。
 * 请按照__字典序__给出所有合法的字符串。
 * 输入描述:
 * 输入为1个正整数
 * 输出描述:
 * 输出为所有合法的字符串,用英文逗号隔开
 * 输入例子1:
 * 2
 * 输出例子1:
 * (()),()()
 *
 * @author shijiacheng
 */
public class FindLegalString {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<String> result = new ArrayList<>();
        printHelper(n, n, "", result);

        Collections.sort(result);
        for (int i = 0; i < result.size(); i++) {
            if (i < result.size() - 1) {
                System.out.print(result.get(i) + ",");
            } else {
                System.out.print(result.get(i));
            }
        }
    }

    private static void printHelper(int left, int right
            , String out, List<String> result) {

        if (left < 0 || right < 0 || left > right) {
            return;
        }
        if (left == 0 && right == 0) {
            result.add(out);
            return;
        }

        printHelper(left - 1, right, out + "(", result);
        printHelper(left, right - 1, out + ")", result);

    }

}
发表于 2018-08-14 23:25:59 回复(0)
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
// 例子: n = 4
// 先添加左括号: str = "" -> str = "((((" -> str = "(((())))"
//              str = "" -> str = "((((" -> str = "(((" -> "((()" ...
 
void process(string & str, vector<string> & res, int nl, int nr, int n) {
    // 若str中左括号的数量和右括号的数量都为n, 则将str添加到结果数组中, 并返回
    if (nl >= n && nr >= n) {
        res.push_back(str);
        return;
    }
    // 原则是先添加左括号
    if (nl < n) { // 左括号的数量不超过n
        str.push_back('(');
        // 注意process每次都添加扩好并删除括号, 返回时对传入的str没有做改变
        process(str, res, nl + 1, nr, n);  
        str.pop_back(); // 删除push_back添加的左括号
    }
    // 若左括号的数量比右括号的多
    if (nl > nr) {
        str.push_back(')'); // 补充一个右括号
        process(str, res, nl, nr + 1, n);
        str.pop_back();
    }
}
 
int main() {
    int n = 0;
    while (cin >> n) {
        string str;
        vector<string> res;
        process(str, res, 0, 0, n);
        cout << res.front();
        for (int i = 1; i < res.size(); ++i) {
            cout << "," << res[i];
        }
        cout << endl;
    }
    return 0;
}

编辑于 2018-08-10 23:00:59 回复(0)
var n = parseInt(line);
    console.log([...new Set(makeString(n))].sort().join(','));
    
    function makeString(n) {
        if (n == 0) {
            return [''];
        }
        var arr = makeString(n - 1), len = arr.length, result = [];
        for(var i = 0; i < len; i++) {
            let s1 = '()' + arr[i];
            result.push(s1);
            if (arr[i].indexOf('(') > -1) {
                let tmp = arr[i].split('');
                tmp.forEach((item, index) => {
                    if (item == '(') {
                        let s2 = '(' + tmp.slice(0, index + 1).join('') + ')' + tmp.slice(index + 1).join('');
                        result.push(s2);
                    }
                });
            }
            let s3 = arr[i] + '()';
            result.push(s3);
        }
        return result;
    }

发表于 2018-08-09 19:37:12 回复(0)
def generate(n):
    res= []
    def dfs(cur_str,left,right,n):
        if left == n and right == n:
            res.append(cur_str)
        if left<right:
            return
        if left<n: 
            dfs(cur_str+'(',left+1,right,n)
        if right<n:
            dfs(cur_str+')',left,right+1,n)
    dfs('',0,0,n)
    return res
n = int(input())
res = generate(n)
print(','.join(res))
发表于 2020-03-26 19:53:02 回复(3)
直接利用next_permutation然后判断是否合法输出就行,下面给出函数:
bool isLegal(string s) {
    int n = s.size();
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += s[i] == '('? 1 : -1;
        if (sum < 0)return false;
    }
    return true;
}

void generate(int n){
    string s = string(n,'(') + string(n,')');
    if(n > 1){
        n *= 2;
        string s1(n,'(');
        for (int i = 1; i < n; i+=2)s1[i] = ')';
        do{
            if(isLegal(s))cout << s << ',';
            next_permutation(s.begin()+1, s.end()-1);
        }while (s != s1);
    }
    cout << s << '\n';
}


发表于 2020-08-07 15:58:26 回复(0)
var n = Number(readline());
var x = n,y = n;
var result = [];
var str = "";
var flag = true;
combine(str,x,y);
function combine(str,x,y){
    if (x <= y) {
        flag = true;
    } else {
        flag = false;
    }
    if (x == 0 && y == 0 && flag) {
        result.push(str);
        return;
    } else if (x == 0 && y == 0){
        return;
    }
    
    if (flag && x >= 0 && y >= 0) {
        combine(str+'(',x-1,y);
        combine(str+')',x,y-1);
    }
}
print(result.join())

发表于 2019-09-05 15:18:33 回复(0)
#include <iostream>
#include<algorithm>
#include <string>
#include <vector>
using namespace std;


void fun(int n, vector<string> &res, string out, int left, int right)
{
    //left目前已经用的左括号的数目,right目前已经用的右括号的数目
	if (left == n && right == n) { res.push_back(out); return; }
	if (left < n) fun(n, res, out + '(', left + 1, right);
	if (right < left) fun(n, res, out + ')', left, right + 1);
}

int main()
{
	int n;
	cin >> n;
	vector<string> res;
	fun(n, res, "", 0, 0);
	cout << res.front();
	for (int i = 1; i < res.size(); i++)
	{
		cout << "," << res[i];
	}
	cout << endl;
	system("pause");
	return 0;
}

发表于 2019-09-03 17:16:34 回复(0)
// 深度优先搜索
#include<iostream>
#include<string>
#include<vector>
 
using namespace std;
 
string l = "(";
string r = ")";
vector<string> res;
 
void dfs(string str, int n, int zero, int one){
    if (zero==n && one==n){
        res.push_back(str);
        return;
    }
    string str0 = str + l;
    string str1 = str + r;
    if(zero==n && one<n) dfs(str1,n,zero,one+1);
    else{
        if(zero>=one) {
            dfs(str0,n,zero+1,one);
            dfs(str1,n,zero,one+1);
        }
    }
}
 
int main(){
    int n;
    cin >> n;
    string init = "";
    dfs(init, n, 0, 0);
    for(inti=0;i<res.size()-1;i++){
        cout << res[i] << ",";
    }
    cout << res[res.size()-1];
}
发表于 2018-08-29 17:23:01 回复(0)
 
c=[]
def Permutation(string, beg, endl):
    if beg == endl - 1:
        c.append(str(string))
        return
    for i in range(beg, endl):
        if string[i] in string[beg:i]:
            continue
        string[i], string[beg] = string[beg], string[i]
        Permutation(string, beg+1, endl)
        string[beg], string[i] = string[i], string[beg]
m=[]
result=[]
cout=0
n=int(input())
l=0
r=1
string=[0]*n+[1]*n
beg = 0
endl = len(string)
Permutation(string, beg, endl)
for x in c:
    for i in x[0:-1]:
        if i=='0':
            cout+=1
        elif i=='1':
            cout-=1
        if cout<0:
            break
    if cout>=0:
        result.append(x)
    cout=0
print(','.join([''.join(ii[1:-1].split(',')).replace('0','(').replace('1',')') for ii in result]).replace(' ',''))






发表于 2018-08-29 12:09:35 回复(0)
#include <stdio.h>
#include <iostream>
using namespace std;
#define MAX   50 
char a[MAX] = { 0 };
void print_a(int n, int r, int l)
{
    int num = 0;
    int i = 0;
    if (r > l) {
        return;
    }

    if (r == 0) {
        while (l) {
            a[n++] = ')';
            l--;
        }
        for (int j = 0; j <= n - 2; j = j + 2) {
            if (a[j] == '(')
                num++;
        }
        if (2*num != n) 
            a[n] = ',';
        else
            a[n] = '\0';
        printf("%s", a);
    }
    else {              // r>0
        if (r == l) {
            a[n] = '(';
            print_a(n + 1, r - 1, l);
        }
        else {
            a[n] = '(';
            print_a(n + 1, r - 1, l);
            a[n] = ')';
            print_a(n + 1, r, l - 1);
        }
    }
    return;

}

int main()
{
    int n;
    cin >> n;
    if ((n % 2 != 0) && (n <= 0)) {
        return -1;
    }
    print_a(0, n, n);

    return 0;
}

发表于 2018-08-29 12:01:19 回复(0)
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<string> solve(int n) {
        if (n == 0)return {};
        vector<vector<string>> all(n+1);
        vector<int> nosplit_flag;//标记all[i]中 ,能否左右分割的位置
        all[0].push_back("");
        nosplit_flag.push_back(-1);
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < all[i - 1].size(); j++) {//( all[i-1] )
                all[i].push_back("(" + all[i - 1][j] + ")");//( all[i-1] ) ,无法左右分割
            }
            nosplit_flag.push_back(all[i - 1].size());
            for (int j = 1; j < i; j++) {
                /*
                可且仅可分割成两部分 ()all[i-1],(())all[i-2],((()))all[i-3],(()()) all[i-3]...
                all_together前组合
                */
                for (int k = 0; k < nosplit_flag[j]; k++) {
                    for (int l = 0; l < all[i - j].size(); l++) {
                        all[i].push_back(all[j][k] + all[i - j][l]);//((()))all[i-3],(()()) all[i-3]
                    }
                }
            }
        }
        sort(all[n].begin(), all[n].end());
        all[n].erase(unique(all[n].begin(), all[n].end()), all[n].end());
        return all[n];
    }
    vector<string> core(int n) {
        vector<string> res;
        string temp = "";
        if (n == 1) {
            res.push_back("()");
            return res;
        }
        vector<string> sub = core(n - 1);
        for (int i = 0; i < sub.size(); i++) {
            string ans1 = "()" + sub[i];
            string ans2 = sub[i] + "()";
            string ans3 = "(" + sub[i] + ")";
            res.push_back(ans3);
            res.push_back(ans1);
            if (ans1 != ans2) {
                res.push_back(ans2);
            }
        }
        return res;
    }
};
int main() {
    Solution a;
    int x;
    while (cin >> x) {
        int i;
        auto res = a.solve(x);
        for (i = 0; i <res.size()-1; i++)
            cout <<res[i] << ",";
        cout << res[i];
    }
    return 0;
}
发表于 2018-08-09 22:16:20 回复(0)