2017.9.9网易校招笔试最后一道编程解答

解答代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
//判断是否是合法括号匹配序列
bool panding(string ss, int n) {
    int count = 0;
    for (int i = 0; i<n; i++) {
        if (ss[i] == '(') {
            count++;
        }
        else if (ss[i] == ')') {
            count--;
        }
        if (count<0)
            return false;
    }
    if (count == 0)
        return true;
    else
        return false;
}
//计算两个串的最长公共字串长度
int lcs_len(string s1, string s2) {

    int len1 = s1.size(), len2 = s2.size();
    if (len1 == 0 || len2 == 0)return 0;
    //定义二维数组dp[i][j]  代表串1从0~i这段与串2从0~j这段的公共子串的最大值
    //赋初值dp[0~len1][0]=0   dp[0][0~len2]=0
    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                //若相等则上层值+1
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                //若不相等则等于交错值中的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

    }
    return dp[len1][len2];
}
int main()
{
    string s;
    while (cin >> s)
    {
        string s2(s);
        int shuzu[20] = { 0 };
        int k = 0;
        sort(s.begin(), s.end());
        int i = 0;
        do {
            int lth =s.length();
            if (panding(s, lth))
            {
                shuzu[i]=lcs_len(s, s2);
                i++;
                k++;
            }
        } while (next_permutation(s.begin(), s.end()));//找出s的所有排列
        sort(shuzu, shuzu + 20);
        int temp=0;
        for (int t = 0; t < 20; t++)
        {
            if (shuzu[t] == shuzu[18])
            {
                temp++;
            }
        }
        cout << temp << endl;
    }
    system("pause");
    return 0;
}