Удалить дополнительную скобку ⇐ C++

[Anonymous]

Вопрос: < /p>

Удалить дополнительные скобки из строки.

e.g. < /p>

((a+b))*c => (a+b)*c
(a+b)+c => (a+b)+c
((a+b)/(c+d)) => ((a+b)/(c+d))
(a+(((b-c)))*d) => (a+(b-c)*d) and so on.
< /code>

Я предложил следующее решение:

Подход: я сканирую строку и помню (используя карту) индекс открывающегося скобку и ли она дополнительная или нет (по умолчанию, она дополнительная). Если я найду закрывающую скобку, я проверяю соответствующее открытие скобки с карты, и если она дополнительная, то удалите оба. < /p>

void removeExtraParentheses(string& S){
map pmap;
for(int i = 0; i < S.size(); i++){
map::iterator it;
if(S.at(i) == '('){
pmap = true;
}
else if(S.at(i) == ')'){
it = pmap.end();
it--;
if(!(*it).second){
pmap.erase(it);
}
else{
S.erase(S.begin() + i);
S.erase(S.begin() + (*it).first);
pmap.erase(it);
i = i - 2;
}
}
else{
if(!pmap.empty()){
it = pmap.end();
it--;
(*it).second= false;
}
}
}
}
< /code>

Сложность времени: O (n2)

space: o (n)

Я не слишком доволен своим решением, потому что я использую дополнительное хранилище и делаю это в квадратичное время. < /p>

Можем ли мы сделать это во время O (n) и O (1) пространство? Если не то, что лучше всего сделать?

Подробнее здесь: https://stackoverflow.com/questions/132 ... arenthesis