678.有效的括号字符串

链接：678.有效的括号字符串
难度：Medium
标签：栈、贪心、字符串、动态规划
简介：给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。

题解 1 - typescript

• 编辑时间：2021-09-17
• 执行用时：80ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：分别统计左括号和*的下标，遍历到右括号时消除。

function checkValidString(s: string): boolean {
  const leftStack: number[] = [];
  const starStack: number[] = [];
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (c === '(') leftStack.push(i);
    else if (c === '*') starStack.push(i);
    else {
      if (leftStack.length === 0 && starStack.length === 0) return false;
      if (leftStack.length !== 0) leftStack.pop();
      else starStack.pop();
    }
  }
  while (leftStack.length !== 0 && starStack.length !== 0) {
    const left = leftStack.pop()!;
    const star = starStack.pop()!;
    if (left > star) return false;
  }
  return leftStack.length === 0;
}

题解 2 - typescript

• 编辑时间：2021-09-17
• 执行用时：68ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：贪心，统计左括号可能的最大值和最小值。

function checkValidString(s: string): boolean {
  let min = 0;
  let max = 0;
  for (const c of s) {
    if (c === '(') {
      min++;
      max++;
    } else if (c === ')') {
      min = Math.max(min - 1, 0);
      max--;
      if (max < 0) return false;
    } else {
      min = Math.max(min - 1, 0);
      max++;
    }
  }
  return min === 0;
}