I'm working on a recursive method clean that extracts the substring inside the outermost parentheses of a string, without the parentheses themselves. The method works as expected, but omits the closing parenthesis ) in cases like "123(45))", where I want the result to be "45)".
My objective: The method should return a new string that contains only the substring inside the outermost parentheses, without the parentheses themselves. If there is no valid pair of parentheses, the method should return an empty string.
The constraints are:
No loops can be used, only recursion.
You can only use the following String methods: charAt, equals, length, substring, and isEmpty.
The input string is guaranteed to be non-null.
public class Main {
public static void main(String[] args) {
String seq = "1(234)67";
System.out.println(clean(seq)); // Expected output: "234"
System.out.println(clean("123(45))")); // Expected output: "45)"
System.out.println(clean("x)")); // Expected output: ""
System.out.println(clean(")x(")); // Expected output: ""
}
public static String clean(String seq) {
if (seq.isEmpty()) {
return "";
}
// If the first character is not '(', remove all characters before it
if (seq.charAt(0) != '(') {
return clean(seq.substring(1));
}
int depth = 0;
int startIdx = -1;
int endIdx = -1;
// Recursively traverse the string to find the outer parentheses
for (int i = 0; i < seq.length(); i++) {
char ch = seq.charAt(i);
if (ch == '(') {
if (depth == 0) {
startIdx = i; // Mark the start of the outer parenthesis
}
depth++;
} else if (ch == ')') {
depth--;
if (depth == 0) {
endIdx = i; // Mark the end of the outer parenthesis
break;
}
}
}
// If an outer parenthesis is found, return the substring without the parentheses
if (startIdx != -1 && endIdx != -1) {
return seq.substring(startIdx + 1, endIdx); // Return the content inside the parentheses
}
// Return an empty string if no valid parentheses are found
return "";
}
}
Current output:
clean("1(234)67") -> "234"
clean("123(45))") -> "45"
clean("x)") -> ""
clean(")x(") -> ""
Expected output:
clean("1(234)67") -> "234"
clean("123(45))") -> "45)"
clean("x)") -> ""
clean(")x(") -> ""
The function works as expected when the string has valid parentheses, but for the string "123(45))", I need the output to be "45)" (including the closing parenthesis )). However, the current implementation returns "45" without the closing parenthesis.
I tried modifying the method, but I'm not sure how to correctly handle cases where the closing parenthesis is not fully enclosed in the outermost pair. The method should still include the closing parenthesis when it is part of the outermost parentheses pair.
So basically, how can I modify the code to ensure that the closing parenthesis ) is included in cases like "123(45))"?
You're seeing "45" instead of "45)" because your code is finding the matching closing parenthesis for the first opening parenthesis you find. But your expected output suggests you shouldn't worry about the parentheses being balanced. You're supposed to be finding the first opening parenthesis and the last closing parenthesis, ignoring any other parenthesis. Then, so long as the opening one comes before the closing one, the result is the substring between those two parenthesis.
Another problem in your code is that you're using a for loop. Your constraints say you cannot use loops at all. You must use recursion.
When looking for the first opening parenthesis, you'll start by checking the character at index 0. If that character is not the correct one, then you check the character at the next index. That's easily implemented as an index loop, but loops are forbidden. Luckily, if you think about it, testing the character at index 1 is essentially the same as testing the character at index 0 of a substring from 1 to length. So, if s.charAt(0) != '(' then recursively call the method with s.substring(1).
Looking for the last closing parenthesis is basically the same process, except you check the last character of the string and use substring to "remove" characters from the end instead of from the start.
All that's left is figuring out the base cases. Those are the cases that terminate the recursion. In this scenario, there are only two base cases:
There's no more string to test (i.e., the string is empty). This means there's no result, and you should return "".
The first character is a ( and the last character is a ). This means a result was found and you should return the substring between those two parentheses.
With all that in mind, a solution to your problem would look something like this:
public class Main {
public static void main(String[] args) {
test("1(234)67"); // Expected output: "234"
test("123(45))"); // Expected output: "45)"
test("x)"); // Expected output: ""
test(")x("); // Expected output: ""
test("12(34)5(67)"); // Expected output: "34)5(67"
}
static void test(String seq) {
var res = clean(seq);
System.out.printf("clean(\"%s\") => \"%s\"%n", seq, res);
}
static String clean(String seq) {
if (seq.isEmpty()) {
// no result
return "";
} else if (seq.charAt(0) != '(') {
// still need to find the first opening parenthesis (recursively)
return clean(seq.substring(1));
} else if (seq.charAt(seq.length() - 1) != ')') {
// still need to find the last closing parenthesis (recursively)
return clean(seq.substring(0, seq.length() - 1));
} else {
// Found result (use 'substring' to remove parentheses from string)
return seq.substring(1, seq.length() - 1);
}
}
}
Output:
clean("1(234)67") => "234"
clean("123(45))") => "45)"
clean("x)") => ""
clean(")x(") => ""
clean("12(34)5(67)") => "34)5(67"
As pointed out, the above solution is not very performant due to all the string copying via substring. A more performant solution would use indices. This requires keeping track of those indices as parameters of the recursive method. Since these indices are implementation details, you typically don't want to expose them via the public API (i.e., the public clean method). A common solution is to introduce a second, private method that performs the actual recursion. Here's an example:
static String clean(String seq) {
return clean(seq, 0, seq.length());
}
private static String clean(String seq, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return "";
}
char first = seq.charAt(startIndex);
char last = seq.charAt(endIndex - 1);
if (first == '(' && last == ')') {
return seq.substring(startIndex + 1, endIndex - 1);
} else if (first != '(') {
return clean(seq, startIndex + 1, endIndex);
} else {
return clean(seq, startIndex, endIndex - 1);
}
}