Medium

题目描述

给定一个只包含三种字符的字符串：'('，')' 和 '*'，写一个函数来检验这个字符串是否为有效字符串。

有效字符串具有如下规则：

  1. 任何左括号 '(' 必须有相对应的右括号 ')'。
  2. 任何右括号 ')' 必须有相对应的左括号 '('。
  3. 左括号 '(' 必须在对应的右括号之前 ')'。
  4. '*' 可以被视为单个右括号 ')' ，或单个左括号 '(' ，或者一个空字符串。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

解题思路

这道题有多种解法，我推荐使用贪心算法，它最高效且易理解。

贪心解法（推荐）

核心思想是维护一个可能的左括号数量的范围 [min_open, max_open]：

  1. min_open: 假设所有 * 都变成 )，最少还需要多少个 (
  2. max_open: 假设所有 * 都变成 (，最多有多少个 (

遍历过程：

  • 遇到 (：min_open 和 max_open 都加1
  • 遇到 )：min_open 减1，max_open 减1
  • 遇到 *：min_open 减1（当作 )），max_open 加1（当作 (）

关键约束：

  • 如果 max_open < 0，说明右括号过多，直接返回 false
  • min_open 不能小于 0，因为左括号数量不能为负

最后检查 min_open 是否为 0，即是否存在完全匹配的可能。

其他解法

双栈解法：分别存储 ( 和 * 的位置，优先用 ( 匹配 )，不够时用 * 补充。

动态规划：dp[i][j] 表示子串 s[i:j+1] 是否有效，但空间复杂度较高。

回溯法：尝试 * 的所有可能，但时间复杂度为 O(3^n)。

代码实现

class Solution {
public:
    bool checkValidString(string s) {
        int min_open = 0, max_open = 0;
        
        for (char c : s) {
            if (c == '(') {
                min_open++;
                max_open++;
            } else if (c == ')') {
                min_open--;
                max_open--;
            } else { // c == '*'
                min_open--;
                max_open++;
            }
            
            if (max_open < 0) return false;
            min_open = max(min_open, 0);
        }
        
        return min_open == 0;
    }
};

class Solution:
    def checkValidString(self, s: str) -> bool:
        min_open = max_open = 0
        
        for c in s:
            if c == '(':
                min_open += 1
                max_open += 1
            elif c == ')':
                min_open -= 1
                max_open -= 1
            else:  # c == '*'
                min_open -= 1
                max_open += 1
            
            if max_open < 0:
                return False
            min_open = max(min_open, 0)
        
        return min_open == 0

public class Solution {
    public bool CheckValidString(string s) {
        int minOpen = 0, maxOpen = 0;
        
        foreach (char c in s) {
            if (c == '(') {
                minOpen++;
                maxOpen++;
            } else if (c == ')') {
                minOpen--;
                maxOpen--;
            } else { // c == '*'
                minOpen--;
                maxOpen++;
            }
            
            if (maxOpen < 0) return false;
            minOpen = Math.Max(minOpen, 0);
        }
        
        return minOpen == 0;
    }
}

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
    let minOpen = 0;
    let maxOpen = 0;
    
    for (let char of s) {
        if (char === '(') {
            minOpen++;
            maxOpen++;
        } else if (char === ')') {
            minOpen--;
            maxOpen--;
        } else {
            minOpen--;
            maxOpen++;
        }
        
        if (maxOpen < 0) return false;
        if (minOpen < 0) minOpen = 0;
    }
    
    return minOpen <= 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
贪心算法O(n)O(1)
双栈法O(n)O(n)
动态规划O(n³)O(n²)
回溯法O(3^n)O(n)

其中 n 为字符串长度。贪心算法是最优解法。

相关题目