Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Post History
You've got an inefficiency in your code, as you always do replacements 3/2 times the length of the string. That is unnecessarily expensive. By instead testing in each iteration whether the length ...
Answer
#1: Initial revision
by
celtschk
·
2021-09-20T07:45:03Z (about 3 years ago)
You've got an inefficiency in your code, as you always do replacements 3/2 times the length of the string. That is unnecessarily expensive.
By instead testing in each iteration whether the length actually changed, you get a much improved performance:
```
def is_valid(s: str) -> bool:
if len(s) % 1 != 0:
return False
# this initial value causes the loop to be skipped entirely for empty strings
prevlen = 0
# stop as soon as no further replacements have been made
while len(s) != prevlen:
prevlen = len(s)
s = s.replace("()", "").replace("[]", "").replace("{}", "")
return len(s) == 0
```
I've put it together with your code and hkotsubo's timing code on tio.run, and got the following:
```
--------------
Unbalanced in the middle
0.04957069695228711
0.002779866976197809
--------------
Unbalanced in the beginning
0.05233071401016787
0.0026999289984814823
--------------
Unbalanced in the end
0.05092682002577931
0.0026755660073831677
--------------
Balanced
0.047405752004124224
0.002398615994025022
```
[Try it online!](https://tio.run/##vVTLjtowFN3nK05BlW3KdBi6Q6KLLvoH7YaiypAbsOrYke2kQohvpzePKRraUVnM9G7i3Oc59zipDmnv3YfzeQwfzM44bdFQiMa7LKcCJn7V1uQyLhBTULj7iI33dpGBzRSw5GRUeIs53iwx6/2tBUp1cPisbaSs8xY@wMA4BO12JIfK@3vM1aUsYon4PlBl9ZbkSKrRFKORunhW62vP8dR7@inD3KH7kjFl2RimrIJvKL/i9r25jdzDP8mNkfYmMjuTTLtCbWvCVteRIkcI1vsKyWNDiD9MVTEUcskEsoduMVRW6dCiMG4Xu45VoIYBoGPQj4iJm@iI6L1rn86jqAO3Dxi2UXLTiL1uiCdxcalz6op/7o2lR0JMZuh@oXQZ1ye9qiLnIvgSyZRkUquND2l4a8UKtcPDrHNEkN7ukSimrNJBly2aI4Sryw0FgQUnTiF21m9YC7HAcJIKpyxrk8VxJaVS66NUK6nWp5PAhItmM46@47BSYjg9m1ixKEmKuyf2zX1xPEm7LUvJl7oVuTR5bkmooaJnJMXvb0iJKSaTnof6M@vxNl6l9TRuwPlSNDbE/wHHF/F1mPwN4PypIDdDJZf/Z5DPQPs0AHthNOdf "Python 3 – Try It Online")