You are seeking from left to right and right to left - this will fail on ([]{})
- even if its valid, cause you would compare [
with }
. (start = 1
and end = 4
)
As a verbal description I would do the following:
- Create a second string of expected values. (Explain this later)
- Iterate over the given string to build up your expectation string, when you find a opening bracket - compare, whenever you find a closing bracket.
Example: The given String is {([])]
.
for i in range(0, length):
- IF opening bracket
[
, {
, (
put the expected closing bracket to the end of the expectation-string. i.e. ]
,}
or )
- ELSE (:= if closing bracket):
- closing bracket matches LAST CHARACTER in the expactation-string? -> remove from expectation-string, proceed.
- closing bracket not matches LAST CHARACTER in the expectation-string? -> invalid format
- expectation-string empty? -> invalid format
- Input-String end reached, expectation-string NOT empty? -> invalid format.
That would process the given string like this:
i | found value | e-string before| e-string after | remark
0 | { | | } | added }
1 | ( | } | }) | added )
2 | [ | }) | })] | added ]
3 | ] | })] | }) | last element was ] -> removed
4 | ) | }) | } | last element was ) -> removed
5 | ] | } | } | found ] but expected } -> invalid.
Edit: Since the expected "Storage complexity" is Oh(n)
as well (not counting input arguments) you will run into a storage complexity of Oh(n)
EXACTLY then, when the given string has n
opening brackets - no problem. But you ofc. should use a second string
then, cause lists have overhead.
For the runtime complexity:
- Setting a value at a certain string position is atomic ->
Oh(1)
(meaning constant)
if()
statements are atomic -> Oh(1)
(meaning constant)
- Removing characters is atomic ->
Oh(1)
(meaning constant)
- Your for loop has
Oh(n)
(depending on n)
Sum it up, you'll get Oh(n)
.
If you like to implement this in Python, you can use http://dog-net.org/string.php to validate your "steps". :-)
ps.: I'm not providing a copy&paste solution on purpose! :P
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…