20.有效的括号

链接：20.有效的括号
难度：Easy
标签：栈、字符串
简介：给定一个只包括 '('，')'，'{'，'}'，'['，']'  的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

题解 1 - java

• 编辑时间：2020-02-16
• 执行用时：2ms
• 内存消耗：40.8MB
• 编程语言：java
• 解法介绍：遍历，左括号压栈，右括号判断。

class Solution {
    public boolean isValid(String s) {
	    	Stack<Character> stack= new Stack<Character>();
	    	int len=s.length();
	    	for(int i =0;i<len;i++) {
	    		char c=s.charAt(i);
	    		if(c=='('||c=='{'||c=='[') {
	    			stack.push(c);
	    		}else {
	    			if(stack.isEmpty())	return false;
	    			char left=stack.pop();
	    			if(left=='('&&c!=')')return false;
	    			if(left=='{'&&c!='}')return false;
	    			if(left=='['&&c!=']')return false;
	    		}
	    	}
	        return stack.isEmpty();
    }
}

题解 2 - java

• 编辑时间：2020-02-16
• 执行用时：4ms
• 内存消耗：41.4MB
• 编程语言：java
• 解法介绍：与 1 思路相似，用 map 储存三对大括号。

class Solution {
    public boolean isValid(String s) {
	    	Stack<Character> stack= new Stack<Character>();
	    	int len=s.length();
	    	for(int i =0;i<len;i++) {
	    		char c=s.charAt(i);
	    		if(c=='('||c=='{'||c=='[') {
	    			stack.push(c);
	    		}else {
	    			if(stack.isEmpty())	return false;
	    			char left=stack.pop();
	    			if(left=='('&&c!=')')return false;
	    			if(left=='{'&&c!='}')return false;
	    			if(left=='['&&c!=']')return false;
	    		}
	    	}
	        return stack.isEmpty();
    }
}

题解 3 - typescript

• 编辑时间：2020-08-14
• 执行用时：92ms
• 内存消耗：38.5MB
• 编程语言：typescript
• 解法介绍：利用栈进行判断。

function isValid(s: string): boolean {
  const stack: string[] = [];
  for (const c of s) {
    if (c === '(' || c === '[' || c === '{') {
      stack.push(c);
    } else {
      const left = stack.pop();
      if (
        !left ||
        (left === '(' && c !== ')') ||
        (left === '[' && c !== ']') ||
        (left === '{' && c !== '}')
      )
        return false;
    }
  }
  return stack.length === 0;
}

题解 4 - typescript

• 编辑时间：2021-03-19
• 执行用时：84ms
• 内存消耗：41MB
• 编程语言：typescript
• 解法介绍：栈维护。

const leftSet = new Set(['(', '[', '{']);
function isValid(s: string): boolean {
  if (s.length === 0) return true;
  const stack: string[] = [];
  for (const c of s) {
    if (leftSet.has(c)) {
      stack.push(c);
    } else if (c === ')') {
      let str = '';
      while (stack.length > 0 && stack[stack.length - 1] !== '(') str = stack.pop()! + str;
      if (stack.length === 0 || stack[stack.length - 1] !== '(') return false;
      stack.pop();
      if (!isValid(str)) return false;
    } else if (c === ']') {
      let str = '';
      while (stack.length > 0 && stack[stack.length - 1] !== '[') str = stack.pop()! + str;
      if (stack.length === 0 || stack[stack.length - 1] !== '[') return false;
      stack.pop();
      if (!isValid(str)) return false;
    } else if (c === '}') {
      let str = '';
      while (stack.length > 0 && stack[stack.length - 1] !== '{') str = stack.pop()! + str;
      if (stack.length === 0 || stack[stack.length - 1] !== '{') return false;
      stack.pop();
      if (!isValid(str)) return false;
    }
  }
  return stack.length === 0;
}

题解 5 - typescript

• 编辑时间：2021-11-24
• 内存消耗：5.8MB
• 编程语言：typescript
• 解法介绍：stack。

typedef struct Stack
{
    int size;
    int len;
    int *data;
} Stack;
Stack *createStack(int len)
{
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->size = 0;
    s->len = len;
    s->data = (int *)malloc(sizeof(int) * len);
    return s;
}
void push(Stack *s, int val)
{
    if (s->size == s->len)
        return;
    s->data[s->size++] = val;
}
void pop(Stack *s)
{
    if (s->size == 0)
        return;
    s->size--;
}
int isEmpty(Stack *s) {
    return s->size == 0;
}
int top(Stack *s)
{
    if (s->size == 0)
        return -999999999;
    return s->data[s->size - 1];
}
void freeStack(Stack *s)
{
    free(s->data);
    free(s);
}
void showStack(Stack *s, char *title, int type)
{
    printf("Stack %s : [", title);
    for (int i = 0; i < s->size; i++)
    {
        i &&printf(",");
        if (type == 1)
            printf("%d", s->data[i]);
        if (type == 2)
            printf("%c", s->data[i]);
    }
    printf("]\n");
}
bool isValid(char * s){
    int len = strlen(s);
    Stack *stack = createStack(len);
    for (int i = 0; i < len; i++) {
        char ch = s[i];
        if (
            ch == ')' && !isEmpty(stack) && s[top(stack)] == '(' ||
            ch == ']' && !isEmpty(stack) && s[top(stack)] == '[' ||
            ch == '}' && !isEmpty(stack) && s[top(stack)] == '{'
        ) pop(stack);
        else push(stack, i);
    }
    return stack->size == 0;
}