Click here to see the full article post
Should not the DP solution's runtime complexity be O(n^3), because of the innermost for loop (k=i+1...)?
If we encounter a left bracket (c == '('), then lo++, otherwise we could write a right bracket, so lo--. If we encounter what can be a left bracket (c != ')'), then hi++, otherwise we could write a left bracket, so hi--
Shouldn't that be "must write a right bracket"?
@robp Thanks, it was corrected.
Empty string is also a possibility, so it is better to change the text "For each asterisk, let's try both possibilities". (Code is correct)
The example for Approach #3 confused me. If we encounter , should lo-- & hi++?
[1, 2, 3] for '(*'
Why not [0,1,2,3]?
@m_scorpio In the article, he said:
[0, 1, 2] for '(*'; [1, 2, 3] for '(**';
Oh, thanks for your correction.
What I am really confused is:
If we encounter
*, should lo-- & hi++?
[1, 2, 3] for '(**'
why not [0,1,2,3]?
In fact, I copied it same as you, but it changed after submission. So sorry for not dealing with the format properly...
@hhsu Thanks. It has been fixed.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.