678. 有效的括号字符串

中等贪心贪心维护未匹配左括号数的范围力扣原题 ↗

题目描述

输入字符串 s，它只由 '('、')' 和 '*' 三种字符组成。

每个 '*' 可以任意当作一个左括号、一个右括号，或者当作空串去掉。

判断能否通过为每个 '*' 选定含义，使 s 成为合法的括号串：每个左括号都有一个位于它右侧的右括号与之配对，每个右括号也都有一个位于它左侧的左括号与之配对。能则返回 true，否则返回 false。

示例 1

输入：s = "()"
输出：true

示例 2

输入：s = "(*)"
输出：true

解释：把 '*' 当作空串即可。

示例 3

输入：s = "(*))"
输出：true

解释：把 '*' 当作左括号，得到 "(())"。

示例 4

输入：s = "("
输出：false

解释：只有一个左括号，无法配对。

数据范围

1 <= s.length <= 100
s[i] 是 '('、')' 或 '*'。

解题思路：贪心维护未匹配左括号数的范围

维护“未匹配左括号数”的可能范围 [lo, hi]。遇到 "(" 两端都加 1；遇到 ")" 两端都减 1；遇到 "*" 时 lo 减 1（当作 ")"）、hi 加 1（当作 "("）。如果 hi < 0，说明即使把所有 * 当作 "(" 右括号也太多，直接失败；未匹配数不能为负，所以把 lo 截到 0。结束时 0 在范围内（lo == 0）即可。

为什么正确

读完前缀后，[lo, hi] 中的每个整数都是某种 * 的取法下的未匹配左括号数，且范围之外的值都不可达。

复杂度分析

时间 O(n)，空间 O(1)。

易错点

必须先检查 hi < 0 再截断 lo；如果忘了截断 lo，"*(" 这类输入会被误判。最后要检查 lo == 0，而不是 hi == 0。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def checkValidString(self, s: str) -> bool:
        lo = hi = 0
        for ch in s:
            if ch == '(':
                lo += 1
                hi += 1
            elif ch == ')':
                lo -= 1
                hi -= 1
            else:
                lo -= 1
                hi += 1
            if hi < 0:
                return False
            lo = max(lo, 0)
        return lo == 0

class Solution {
    public boolean checkValidString(String s) {
        int lo = 0, hi = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                lo += 1;
                hi += 1;
            } else if (ch == ')') {
                lo -= 1;
                hi -= 1;
            } else {
                lo -= 1;
                hi += 1;
            }
            if (hi < 0)
                return false;
            lo = Math.max(lo, 0);
        }
        return lo == 0;
    }
}

class Solution {
public:
    bool checkValidString(string s) {
        int lo = 0, hi = 0;
        for (char ch : s) {
            if (ch == '(') {
                lo += 1;
                hi += 1;
            } else if (ch == ')') {
                lo -= 1;
                hi -= 1;
            } else {
                lo -= 1;
                hi += 1;
            }
            if (hi < 0)
                return false;
            lo = max(lo, 0);
        }
        return lo == 0;
    }
};

func checkValidString(s string) bool {
	lo, hi := 0, 0
	for _, ch := range s {
		if ch == '(' {
			lo += 1
			hi += 1
		} else if ch == ')' {
			lo -= 1
			hi -= 1
		} else {
			lo -= 1
			hi += 1
		}
		if hi < 0 {
			return false
		}
		if lo < 0 {
			lo = 0
		}
	}
	return lo == 0
}

var checkValidString = function(s) {
    let lo = 0, hi = 0;
    for (const ch of s) {
        if (ch === '(') {
            lo += 1;
            hi += 1;
        } else if (ch === ')') {
            lo -= 1;
            hi -= 1;
        } else {
            lo -= 1;
            hi += 1;
        }
        if (hi < 0)
            return false;
        lo = Math.max(lo, 0);
    }
    return lo === 0;
};

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

载入编辑器，自己跑一遍 →

其他解法

区间动态规划按定义枚举，最慢；双栈把星号当作备用括号，按位置匹配；贪心只记未匹配左括号数的上下界，常数空间。

解法 2：双栈时间 O(n)，空间 O(n)

用两个栈分别存放左括号和星号的下标。遇到右括号时，优先弹出一个左括号；没有左括号就弹出一个星号；都没有就无效。遍历结束后，剩下的左括号要用其右侧的星号当作右括号来匹配：两栈同时弹出，若左括号下标大于星号下标就无效。最后左括号栈为空即有效。

沿用普通括号匹配的栈思路，容易理解。需要 O(n) 空间存下标。

class Solution:
    def checkValidString(self, s: str) -> bool:
        left, star = [], []
        for i, ch in enumerate(s):
            if ch == '(':
                left.append(i)
            elif ch == '*':
                star.append(i)
            elif left:
                left.pop()
            elif star:
                star.pop()
            else:
                return False
        while left and star:
            if left.pop() > star.pop():
                return False
        return not left

class Solution {
    public boolean checkValidString(String s) {
        Deque<Integer> left = new ArrayDeque<>(), star = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') left.push(i);
            else if (ch == '*') star.push(i);
            else if (!left.isEmpty()) left.pop();
            else if (!star.isEmpty()) star.pop();
            else return false;
        }
        while (!left.isEmpty() && !star.isEmpty()) {
            if (left.pop() > star.pop()) return false;
        }
        return left.isEmpty();
    }
}

class Solution {
public:
    bool checkValidString(string s) {
        vector<int> left, star;
        for (int i = 0; i < (int)s.size(); i++) {
            char ch = s[i];
            if (ch == '(') left.push_back(i);
            else if (ch == '*') star.push_back(i);
            else if (!left.empty()) left.pop_back();
            else if (!star.empty()) star.pop_back();
            else return false;
        }
        while (!left.empty() && !star.empty()) {
            if (left.back() > star.back()) return false;
            left.pop_back();
            star.pop_back();
        }
        return left.empty();
    }
};

func checkValidString(s string) bool {
	left, star := []int{}, []int{}
	for i := 0; i < len(s); i++ {
		switch {
		case s[i] == '(':
			left = append(left, i)
		case s[i] == '*':
			star = append(star, i)
		case len(left) > 0:
			left = left[:len(left)-1]
		case len(star) > 0:
			star = star[:len(star)-1]
		default:
			return false
		}
	}
	for len(left) > 0 && len(star) > 0 {
		if left[len(left)-1] > star[len(star)-1] {
			return false
		}
		left = left[:len(left)-1]
		star = star[:len(star)-1]
	}
	return len(left) == 0
}

var checkValidString = function(s) {
    const left = [], star = [];
    for (let i = 0; i < s.length; i++) {
        const ch = s[i];
        if (ch === '(') left.push(i);
        else if (ch === '*') star.push(i);
        else if (left.length) left.pop();
        else if (star.length) star.pop();
        else return false;
    }
    while (left.length && star.length) {
        if (left.pop() > star.pop()) return false;
    }
    return left.length === 0;
};

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

解法 3：区间动态规划时间 O(n³)，空间 O(n²)

dp[i][j] 表示 s[i..j] 能否成为有效括号串。单个星号有效；长度为 2 时，左字符是 ( 或 *、右字符是 ) 或 * 就有效。更长的区间有两种来源：两端可以配成一对且 dp[i + 1][j − 1] 为真；或者存在分割点 k，使 dp[i][k] 和 dp[k + 1][j] 都为真。

直接对应“有效串 = 外层包一对括号或两串拼接”的定义，容易证明正确。时间 O(n³)，只适合本题 n ≤ 100 的规模。

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = s[i] == '*'
        for i in range(1, n):
            dp[i - 1][i] = s[i - 1] in '(*' and s[i] in ')*'
        for i in range(n - 3, -1, -1):
            for j in range(i + 2, n):
                if s[i] in '(*' and s[j] in ')*' and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    continue
                for k in range(i, j):
                    if dp[i][k] and dp[k + 1][j]:
                        dp[i][j] = True
                        break
        return dp[0][n - 1]

class Solution {
    public boolean checkValidString(String s) {
        int n = s.length();
        char[] c = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = c[i] == '*';
        for (int i = 1; i < n; i++) dp[i - 1][i] = (c[i - 1] == '(' || c[i - 1] == '*') && (c[i] == ')' || c[i] == '*');
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                if ((c[i] == '(' || c[i] == '*') && (c[j] == ')' || c[j] == '*') && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    continue;
                }
                for (int k = i; k < j && !dp[i][j]; k++) {
                    dp[i][j] = dp[i][k] && dp[k + 1][j];
                }
            }
        }
        return dp[0][n - 1];
    }
}

class Solution {
public:
    bool checkValidString(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        auto open = [&](int i) { return s[i] == '(' || s[i] == '*'; };
        auto close = [&](int i) { return s[i] == ')' || s[i] == '*'; };
        for (int i = 0; i < n; i++) dp[i][i] = s[i] == '*';
        for (int i = 1; i < n; i++) dp[i - 1][i] = open(i - 1) && close(i);
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                if (open(i) && close(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    continue;
                }
                for (int k = i; k < j && !dp[i][j]; k++) {
                    dp[i][j] = dp[i][k] && dp[k + 1][j];
                }
            }
        }
        return dp[0][n - 1];
    }
};

func checkValidString(s string) bool {
	n := len(s)
	open := func(i int) bool { return s[i] == '(' || s[i] == '*' }
	close := func(i int) bool { return s[i] == ')' || s[i] == '*' }
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
		dp[i][i] = s[i] == '*'
	}
	for i := 1; i < n; i++ {
		dp[i-1][i] = open(i-1) && close(i)
	}
	for i := n - 3; i >= 0; i-- {
		for j := i + 2; j < n; j++ {
			if open(i) && close(j) && dp[i+1][j-1] {
				dp[i][j] = true
				continue
			}
			for k := i; k < j && !dp[i][j]; k++ {
				dp[i][j] = dp[i][k] && dp[k+1][j]
			}
		}
	}
	return dp[0][n-1]
}

var checkValidString = function(s) {
    const n = s.length;
    const open = (i) => s[i] === '(' || s[i] === '*';
    const close = (i) => s[i] === ')' || s[i] === '*';
    const dp = Array.from({ length: n }, () => new Array(n).fill(false));
    for (let i = 0; i < n; i++) dp[i][i] = s[i] === '*';
    for (let i = 1; i < n; i++) dp[i - 1][i] = open(i - 1) && close(i);
    for (let i = n - 3; i >= 0; i--) {
        for (let j = i + 2; j < n; j++) {
            if (open(i) && close(j) && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                continue;
            }
            for (let k = i; k < j && !dp[i][j]; k++) {
                dp[i][j] = dp[i][k] && dp[k + 1][j];
            }
        }
    }
    return dp[0][n - 1];
};

function checkValidString(s: string): boolean {
    const n = s.length;
    const open = (i: number): boolean => s[i] === '(' || s[i] === '*';
    const close = (i: number): boolean => s[i] === ')' || s[i] === '*';
    const dp = Array.from({ length: n }, () => new Array(n).fill(false));
    for (let i = 0; i < n; i++) dp[i][i] = s[i] === '*';
    for (let i = 1; i < n; i++) dp[i - 1][i] = open(i - 1) && close(i);
    for (let i = n - 3; i >= 0; i--) {
        for (let j = i + 2; j < n; j++) {
            if (open(i) && close(j) && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                continue;
            }
            for (let k = i; k < j && !dp[i][j]; k++) {
                dp[i][j] = dp[i][k] && dp[k + 1][j];
            }
        }
    }
    return dp[0][n - 1];
}

贪心专题的其他题目

查看贪心全部题目 →