Блог пользователя BaOH2

A question about bracket strings
Автор BaOH2, история, 6 лет назад, По-английски

Could you please answer my question, thank you very much!

here are some laws about legal bracket strings:

  • an empty string is a legal bracket string
  • if A is a legal bracket string, so (A) is a legal bracket string
  • if A is a legal bracket string and B is a legal bracket string, so AB is a legal bracket string

And I want to know that what is the minimum edits that letting a bracket string to be legal?

Thank you so much!

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
← Rev. 5  
Проголосовать: нравится +3 Проголосовать: не нравится

Is there a place to submit, I have this greedy idea

cnt = 0

diff = 0 /// count('(') - count(')')
For each char &c in string in normal order
-- if (c = '(') ++diff else --diff
-- if (diff < 0)
---- c = '('
---- diff += 2
---- cnt += 1

diff = 0 /// count(')') - count('(')
For each char &c in string in reverse order
-- if (c = ')') ++diff else --diff
-- if (diff < 0)
---- c = ')'
---- diff += 2
---- cnt += 1

out << cnt
→ Ответить