Sponsored
Sponsored
This approach utilizes a single counter to track the current depth of nesting while iterating through the string. Whenever an open parenthesis '(' is encountered, the counter is incremented, and whenever a closing parenthesis ')' is encountered, the counter is decremented. The maximum value of the counter at any point during the iteration is recorded as the maximum nesting depth.
Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), as only a few variables are used.
1def maxDepth(s: str) -> int:
2 current_depth = 0
3 max_depth = 0
4 for c in s:
5 if c == '(':
6 current_depth += 1
7 if current_depth > max_depth:
8 max_depth = current_depth
9 elif c == ')':
10 current_depth -= 1
11 return max_depth
12
13s = "(1+(2*3)+((8)/4))+1"
14print("Max Depth:", maxDepth(s))This Python function similarly loops over each character in the string, adjusting the depth counter, and records the maximum depth encountered.
This approach uses a stack to simulate the depth of nested parentheses. Each time an open parenthesis '(' is encountered, it is pushed onto the stack, and for each closing parenthesis ')', an item is popped. The maximum size of the stack during this process reflects the maximum nesting depth.
Time Complexity: O(n). Space Complexity: O(n) due to stack usage.
1
The C code uses an array as a stack to keep track of open parentheses. The depth is reflected by the top index of the stack, which indicates the number of open parentheses nested relatively.