Check if the Depth of Parentheses is correct in the given String in Java
The depth of parentheses in a string refers to the level of nesting of parentheses, indicating how many levels of enclosing pairs of parentheses contain a given portion of the string. It measures the hierarchical structure formed by nested pairs of opening and closing parentheses.
Example 1:
Input: S = “((2))(3)”
Output: No
Explanation: The integer 2 is enclosed by two opening and closing parentheses, indicating a depth of two.
The integer 3 is surrounded by one open and one closing parenthesis, indicating a depth of one.
Because the depths indicated by integers 2 and 3 do not correspond to the actual depths of the parentheses surrounding them, the output is "No".
Example 2:
Input: S = "((2)((3)))"
Output: Yes
Explanation: The input "S = "((2)((3)))" is a string with two integers, 2 and 3, respectively. The input contains two opening and closing parentheses, indicating a depth of 2, and the integer itself, 3, matching the depth indicated by the parentheses. The output is "Yes", confirming the correct depth of parentheses.
Using Brute-force Approach
The code validates the depth of parentheses within a string. It iterates through each character in the string, keeping track of the depth of the nested parentheses. When it encounters an opening parenthesis, it increases the depth counter. When it encounters a closing parenthesis, it decrements the depth counter. If it encounters a digit, it compares the current depth to its numeric value. If they are not the same, it returns "No". Finally, it returns "Yes" if the depth counter is zero after traversing the entire string, indicating that all parentheses have been correctly matched; otherwise, it returns "No".
Here's an implementation of checking the depth of the parantheses in a given string using a brute-force approach :
FileName: DepthOfParentheses.java
public class DepthOfParentheses { // Function to check if the depth of parentheses is correct public static String checkDepth(String S) { int depth = 0; // Initialize depth counter for (int i = 0; i < S.length(); i++) { char ch = S.charAt(i); // Get current character if (ch == '(') { // If current character is an opening parenthesis depth++; } else if (ch == ')') { // If current character is a closing parenthesis depth--; } else if (Character.isDigit(ch)) { // If current character is a digit int num = Character.getNumericValue(ch); // Get numeric value of digit if (depth != num) { return "No"; } } } return depth == 0 ? "Yes": "No"; // If depth is zero, return "Yes", otherwise "No" } public static void main(String[] args) { String S = "((2)((3)))"; System.out.println( checkDepth(S)); } }
Output:
Yes
Complexity analysis: The time complexity of the above approach is O(n), where n represents the length of the input string S and Space complexity is O(1), as space usage remains constant regardless of input size.
Using Optimized Approach
The code uses an optimized approach to check the depth of parentheses in an input string. It initializes a variable `depth`, iterates through each character, increments or decrements the depth for opening and closing parenthesis, and processes digits. If the depth matches the numeric value of a digit, it returns "No." The final depth is checked, and if it's 0, all parentheses are correctly matched.
Here's an implementation of checking the depth of the parantheses in a given string using an optimized approach :
FileName: DepthOfParentheses1.java
public class DepthOfParentheses1 { // Function to check if the depth of parentheses is correct public static String checkDepth(String S) { int depth = 0; for (char ch : S.toCharArray()) { if (ch == '(') { // If character is an opening parenthesis depth++; } else if (ch == ')') { // If character is a closing parenthesis depth--; } else if (Character.isDigit(ch)) { // If character is a digit if (depth != Character.getNumericValue(ch)) { // If current depth does not match the digit value return "No"; } } } // If at the end, depth is 0, return "Yes" indicating correct depth, otherwise return "No" return depth == 0 ? "Yes": "No"; } public static void main(String[] args) { String S = "((2)((3)))"; System.out.println(checkDepth(S)); } }
Output:
Yes
Complexity analysis: The code's time complexity is O(n), where n is the input string's length. The only additional space used is the integer variable `depth`, which takes O(1) space regardless of the input string's size. Thus, the code's time and space complexity are O(n).