[伯俊]括弧#2800を削除

21215 ワード
白駿 2800 テキストリンク
説明:
久しぶりに黄金の問題をして、本当に難しいです.
回帰によりdfsを実現し,問題を解決した.
カッコペアのインデックスを使用して、カッコペアを削除するかどうかを決定します.resultに入れます.((0))に類似するinputがあれば、1番目の丸カッコ対を外し、2番目の丸カッコ対を外し、結果は同じであるため、resultの資料型をSetとして重複データ消去を行い、結果を出力する.
Node.説明する
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();

const solution = (str) => {
  const stack = [];
  const brackets = [];
  const result = new Set();
  const selected = new Array(str.length).fill(true);

  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(') stack.push(i);
    else if (str[i] === ')') brackets.push([stack.pop(), i]);
  }

  const dfs = (idx, cnt) => {
    if (idx === brackets.length) {
      if (cnt > 0) {
        let temp = '';
        for (let i = 0; i < str.length; i++) {
          if (selected[i]) temp += str[i];
        }
        result.add(temp);
      }
      return;
    }
    dfs(idx + 1, cnt);
    selected[brackets[idx][0]] = false;
    selected[brackets[idx][1]] = false;
    dfs(idx + 1, cnt + 1);
    selected[brackets[idx][0]] = true;
    selected[brackets[idx][1]] = true;
  };
  dfs(0, 0);
  return [...result].sort().reduce((acc, cur) => acc + cur + '\n', '');
};

console.log(solution(input));
C++プール
#include <bits/stdc++.h>
using namespace std;

string str;
bool selected[203];
vector<pair<int, int>> brackets;
set<string> result_set;

void dfs(int idx, int cnt) {
    if (idx == brackets.size()) {
        if (cnt > 0) {
            string tmp = "";
            for (int i=0; i<str.length(); i++) {
                if (selected[i]) tmp += str[i];
            }
            result_set.insert(tmp);
        }
        return;
    }
    dfs(idx + 1, cnt);
    selected[brackets[idx].first] = false;
    selected[brackets[idx].second] = false;
    dfs(idx + 1, cnt + 1);
    selected[brackets[idx].first] = true;
    selected[brackets[idx].second] = true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    stack<int> S;
    cin >> str;
    for (int i=0; i<str.length(); i++) {
        selected[i] = true;
        if (str[i] == '(') S.push(i);
        else if (str[i] == ')') {
            brackets.push_back({ S.top(), i });
            S.pop();
        }
    }
    
    dfs(0, 0);
    for (auto result : result_set) cout << result << '\n';
    
    return 0;
}
[コケ]行列-1764、リスニング雑誌
MySQLの追加削除とテーブルのコピーと名前変更