Description#
Given a string containing only the characters '(', ')', '{', '}', '[', ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
Approach#
- My first thought is to use the push and pop operations of a stack. Push the left parentheses and pop the right parentheses. If the right parentheses do not match the top left parentheses of the stack, return false.
- After looping through the string, if the length of the stack is 0, return true; otherwise, return false.
void push(char* dir,int* now_size,char get) {
int size = *now_size;
for(;size;size--)
dir[size] = dir[size - 1];
dir[size] = get;
(*now_size)++;
}
void pop(char* dir,int* now_size) {
for(int i=0;i<(*now_size);i++)
dir[i] = dir[i + 1];
dir[*now_size] == '\0';
(*now_size)--;
}
bool isValid(char * s){
if(*s == '\0')//return true for empty string
return true;
char get[10000] = "\0";
int size = 0;
for(int i=0;s[i] != '\0';i++) {
if(s[i] == '(' || s[i] == '[' || s[i] == '{')
push(get,&size,s[i]);
else {
if(s[i] - get[0] < 3 && s[i] - get[0] > 0)//parentheses match
pop(get,&size);
else
return false;
}
}
if(size != 0)
return false;
return true;
}
- Since the length of the string is unknown, the length of the stack is set to a large value, making the steps somewhat cumbersome.
Advanced Approach#
- Use the string itself without using additional memory to perform stack-like operations.
- Traverse the string and when encountering a left parenthesis, do nothing. When encountering a right parenthesis, check if the previous parenthesis matches it. If it matches, remove both parentheses; otherwise, return false. If the previous parenthesis cannot be found, return false.
- During the traversal, record the number of left parentheses. Decrease the count when removing parentheses. After the traversal, if the count of left parentheses is not zero, return false; otherwise, return true.
bool isValid(char * s){
if(*s == '\0')//return true for empty string
return true;
int left = 0;
for(int i = 0;s[i] != '\0';i++) {
if(s[i] == ')' || s[i] == ']' || s[i] == '}') { //start removing parentheses when encountering a right parenthesis
for(int j = i - 1;j >= -1;j--) {
if(j == -1) //cannot find the previous parenthesis
return false;
if(s[j] != '\0' && j >= 0) { //check the previous parenthesis
if(s[i] - s[j] < 3 && s[i] - s[j] > 0) {//the previous parenthesis matches the current parenthesis
left--; //decrease the count of left parentheses
s[i] = s[j] = '\0'; //remove the parentheses
break;
}
else //the previous parenthesis does not match the current parenthesis
return false;
}
}
}
else left++; //increase the count of left parentheses
}
if(left)
return false;
return true;
}
- It seems to be fine, but the runtime is still quite long. I will optimize it later.