Исправить скобки Алгоритм - PullRequest
Новая
       52

Исправить скобки Алгоритм

0 голосов
/ 20 апреля 2020

Учитывая строку, содержащую только символы '(', ')', '{', '}', '[' и ']', вы должны сделать ее действительной.

Этот вопрос отличается от проблемы LeetCode Classi c. Этот вопрос в основном просит вас сделать его действительным, исправив его.

Если я дам вам строку: "{(}("

Вы должны вернуть мне новую строку, в которой скобки совпадают: {()} или (){}

Это не так как удаление проблемы с круглыми скобками. Вы можете добавить, но не можете удалить.

Итак, если дано (, вы должны вернуть ().

Вот мой код, но я понимаю, что он удваивает скобки. Буду признателен, если кто-то может дать более эффективное решение. 

def parentheses_fix(paran):
    stack = []
    valid = []
    dictionaryOpen = {'(':')','{':'}','[':']'}
    dictionaryClosed = {')':'(', '}':'{', ']':'['}
    for i in range(len(paran)):
        if paran[i] in dictionaryOpen.keys():
                stack.append(paran[i])
                valid.append(paran[i])
        elif paran[i] in dictionaryOpen.values():
            if len(stack) > 0:
                g = stack.pop()
                #closed paranthesis
                valid.append(dictionaryOpen[g])
                valid.append(dictionaryClosed[paran[i]])
                valid.append(paran[i])
            else:
                valid.append(dictionaryClosed[paran[i]])
                valid.append(paran[i])
    for i in range(len(stack)):
        valid.append(dictionaryOpen[stack[-(1+i)]])
    return ''.join(valid)

1 Ответ

0 голосов
/ 20 апреля 2020

Насколько я понимаю, для вас не имеет значения, сколько раз мы меняем направление символа или меняем положение символов, поэтому это поможет: 

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

string buildPar(int par){
    if(par == 0) return ""; 
    return "(" + buildPar(par - 1) + ")";
}

string buildCol(int col, int par){
    if(col == 0) return buildPar(par); 
    return "[" + buildCol(col - 1, par) + "]";
}

string buildCha(int cha, int col, int par){
    if(cha == 0) return buildCol(col, par); 
    return "{" + buildCha(cha - 1, col, par) + "}";
}

int main(){
    string pat = "{(}(()][{{]}()}";

    int par = 0, col = 0, cha = 0;

    for(int i = 0; i < pat.size(); i++){
        if(pat[i] == '(' || pat[i] == ')') par++; 
        else if(pat[i] == '[' || pat[i] == ']') col++; 
        else cha++; 
    }

    if(par % 2 == 1) par++;
    if(col % 2 == 1) col++;
    if(cha % 2 == 1) cha++;

    string ans = buildCha(cha / 2, col / 2, par / 2);      
   cout<<ans<<endl;      
}

Код в основном подсчитывает все (, ), [, ], { и }. Мы просто сопоставляем каждую пару одного типа. Если оба являются ( и (, предположим, что мы меняем направление одного из них. Если существует нечетное число определенного типа c, добавьте еще одно. Затем измените положение всех из них, чтобы они точно совпадали. 

OUTPUT: {{{[[((()))]]}}}
...