educative.io

The two codes solve different problems

Courses
,
#1

The first code allows a closing bracket to be matched to any matching opening bracket that appears before it while the latter code only allows it if it is the last opening bracket it sees.

Case in point for the former code
cout << is_balanced("([)]");
returns true

While for the latter code it returns false.

Course: Competitive Programming in C++: The Keys to Success - Learn Interactively
Lesson: Solved Problem - Balanced Parentheses Sequence - Competitive Programming in C++: The Keys to Success

#2

Hello Hao,
The second code provide a optimized solution to the problem. In second code:

  • If the latter bracket is not closing first, it will give False.
  • If the sequence is “([)]”, it will return False as it should be “[()]” to return True.

Happy Learning :slight_smile:

#3

The second code solves a different problem than the first.

As I mentioned

cout << is_balanced("([)]");`

returns Yes in the first (brute force) code but returns No in the second (optimized ) code.

#4

The second code solves the same problem, but in optimized way.

The first code returns Yes whenever it finds the closing bracket, but the second code returns Yes If the latter bracket is closing first. The solving pattern is different, but the problem is still the same.

#5

Call cout << is_balanced("([)]"); on both codes the first returns yes the second returns no. When I give cout << is_balanced("([)]"); to the first code it returns yes and when I give it to the second it returns no please check this.

#6

But that means the codes are solving different problems. If one is merely an optimized version of the other then the outputs should be the same. But cout << is_balanced("([)]");` gives different outputs for the bruteforce and optimized version so they are solving different problems.