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

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

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
  • Проголосовать: не нравится

»
4 года назад, # |
← 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
→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thank you for helping me and i am soooooooo sorry that i didn't log into this account yesterday and i did not see this answer

    and i really want to say thank you for solving a kind of strange question :)

    i will study hard tomorrow :)

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Sometimes ad-hoc/implementation problems takes time to solve whatever your level is. It is ok bro

      → Ответить