Remove Invalid Parentheses in Java
The "Remove Invalid Parentheses" problem is a crucial problem in computer science and string manipulation, aiming to remove the minimum number of parentheses required for an expression to be valid. It is applied in fields like natural language processing, compiler design, and algorithmic programming interviews.
Example:
Input: s = "()())()"
Output: ["(())()","()()()"]
Explanation: The input string's = '()())()' is analyzed to identify invalid parentheses. The first unmatched close parenthesis is removed to generate valid expressions, resulting in balanced parentheses.
Using BFS
The code uses ArrayList, HashSet, LinkedList, and Queue to manage states and track visited states. It uses a breadth-first search (BFS) traversal to remove invalid parentheses from a string. The isValid() function checks if a string contains valid parentheses by counting the number of opening and closing parentheses.
Here's an implementation of removing invalid parenthesis using bfs :
FileName: RemoveInvaildParentheses .java
import java.util.ArrayList; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Set; public class RemoveInvaildParentheses { // Function to remove invalid parentheses from the input string public ListremoveInvalidParentheses(String s) { List res = new ArrayList<>(); // Sanity check: If the input is null, return an empty list if (s == null) return res; // Set to keep track of visited states to avoid duplicates Set visited = new HashSet<>(); // Queue for BFS traversal of all possible states Queue queue = new LinkedList<>(); // Initialize the queue and mark the initial state as visited queue.add(s); visited.add(s); // Flag to track if a valid expression has been found boolean found = false; // BFS traversal while (!queue.isEmpty()) { s = queue.poll(); // If the current state is valid, add it to the result if (isValid(s)) { res.add(s); found = true; } // If a valid expression is found, continue to the next iteration if (found) continue; // Generate all possible states by removing a single left or right parenthesis for (int i = 0; i < s.length(); i++) { // We only try to remove left or right paren if (s.charAt(i) != '(' && s.charAt(i) != ')') continue; // Generate the next state by removing the current parenthesis String t = s.substring(0, i) + s.substring(i + 1); // If the state is not visited, add it to the queue and mark it as visited if (!visited.contains(t)) { queue.add(t); visited.add(t); } } } return res; } // Helper function to check if a string contains valid parentheses boolean isValid(String s) { int count = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '(') count++; if (c == ')' && count-- == 0) return false; } return count == 0; } public static void main(String[] args) { RemoveInvaildParentheses sol = new RemoveInvaildParentheses(); String input = "()())()"; List result = sol.removeInvalidParentheses(input); System.out.println( result); } }
Output:
[(())(), ()()()]
Complexity analysis: O(2^N), where N represents the length of the input string. The reason is that, in the worst-case scenario, the algorithm investigates all possible methods of removing parentheses. O(2^N), where N represents the length of the input string. It is due to the amount of space required to store the visited states, as well as the queue used in BFS traversal, which can grow exponentially as the input string length increases.
Using Backtracking
The code recursively removes invalid parentheses from a given string. It determines the number of invalid parentheses to remove based on the number of unmatched parentheses. Then, it generates valid expressions recursively, removing parentheses one at a time. The isValid() function determines whether a string has valid parentheses by comparing the opening and closing parentheses on a stack.
Here's an implementation of removing invalid parenthesis using backtracking :
FileName: RemoveInvalidParentheses1.java
import java.util.ArrayList; import java.util.List; import java.util.Stack; public class RemoveInvalidParentheses1 { // Function to remove invalid parentheses public ListremoveInvalidParentheses(String s) { List list = new ArrayList<>(); Stack stack = new Stack<>(); int m = isValid(s); // Get initial number of invalid parentheses int open = 0, close = 0; // Count the number of parentheses to remove for (char c : s.toCharArray()) { if (c == '(') open++; else if (c == ')') { if (open > 0) open--; else close++; } } // Recursive helper function to generate valid expressions removeInvalidParenthesesHelper(s, 0, open, close, list); return list; } // Helper function for recursive removal of invalid parentheses private void removeInvalidParenthesesHelper(String s, int index, int open, int close, List list) { if (open == 0 && close == 0) { int check = isValid(s); if (check == 0) { list.add(s); } return; } for (int i = index; i < s.length(); i++) { if (i > index && s.charAt(i) == s.charAt(i - 1)) continue; if (s.charAt(i) == '(' && open > 0) { String newStr = s.substring(0, i) + s.substring(i + 1); removeInvalidParenthesesHelper(newStr, i, open - 1, close, list); } if (s.charAt(i) == ')' && close > 0) { String newStr = s.substring(0, i) + s.substring(i + 1); removeInvalidParenthesesHelper(newStr, i, open, close - 1, list); } } } // Function to check if a string has valid parentheses public int isValid(String s) { Stack stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') stack.push(s.charAt(i)); // Push open parenthesis to stack else if (s.charAt(i) == ')') { // If it's a close parenthesis if (!stack.isEmpty() && stack.peek() == '(') stack.pop(); // Match with open parenthesis else stack.push(s.charAt(i)); // Otherwise, push to stack } } return stack.size(); } public static void main(String[] args) { RemoveInvalidParentheses1 sol = new RemoveInvalidParentheses1(); String input = "()())()"; List result = sol.removeInvalidParentheses(input); System.out.println( result); System.out.println(); } }
Output:
[(())(), ()()()]
Complexity analysis: O(2^N), where N represents the length of the input string. It happens because, in the worst-case scenario, the recursive function investigates all possible methods of removing parentheses. O(N) is the space complexity of the above code, where N represents the length of the input string. It happens because the stack takes up space during the isValid() function, as well as the recursive function call stack, which can grow to be as long as the input string itself.