Description of the problem from the coding:
String S, consisting of N characters, is considered correctly nested if one of the following conditions is true:
S is empty; S has the form "(U)" or "[U]" or "{U}", where U is a correctly nested string; S has the form "VW", where V and W are correctly nested strings. For example, the string "{[() ()]}" is correctly nested, but "([) ()]" is not.
Write a function:
class Solution {public int solution (String S); }
which, given the string S, consisting of N characters, returns 1 if S is correctly nested and 0 otherwise.
For example, if S = "{[() ()]}", the function should return 1 and set S = "([) ()]", the function should return 0, as explained above.
Let's pretend that:
N is an integer in the range [0,200,000]; string S consists only of the following characters: "(", "{", "[", "]", "}" and / or ")". Complexity:
expected worst-case time complexity - O (N); the expected worst spatial complexity is O (N) (not counting the storage required for the input arguments).
I get 87%. I can not understand the problem.
Here is my code:
import java.util.Stack;
class Solution {
public int solution(String s) {
if (s.length() % 2 != 0) {
return 0;
}
Character openingBrace = new Character('{');
Character openingBracket = new Character('[');
Character openingParen = new Character('(');
Stack<Character> openingStack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == openingBrace || c == openingBracket || c == openingParen) {
openingStack.push(c);
} else {
if (i == s.length()-1 && openingStack.size() != 1) {
return 0;
}
if (openingStack.isEmpty()) {
return 0;
}
Character openingCharacter = openingStack.pop();
switch (c) {
case '}':
if (!openingCharacter.equals(openingBrace)) {
return 0;
}
break;
case ']':
if (!openingCharacter.equals(openingBracket)) {
return 0;
}
break;
case ')':
if (!openingCharacter.equals(openingParen)) {
return 0;
}
break;
default:
break;
}
}
}
return 1;
}
}