class Solution {
public:
bool checkValidString(string s) {
}
};
678. 有效的括号字符串
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
( 必须有相应的右括号 )。) 必须有相应的左括号 ( 。( 必须在对应的右括号之前 )。* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。示例 1:
输入: "()" 输出: True
示例 2:
输入: "(*)" 输出: True
示例 3:
输入: "(*))" 输出: True
注意:
相似题目
原站题解
python3 解法, 执行用时: 48 ms, 内存消耗: 16 MB, 提交时间: 2023-09-24 23:31:05
'''
贪心
遍历两次，第一次顺序，第二次逆序。
第一次遇到左括号加一，右括号减一，星号加一，最后保证cnt >= 0,也就是可以保证产生的左括号足够
第二次遇到右括号加一，左括号减一，星号加一，最后保证cnt >= 0,也就是可以保证产生的右括号足够
当两次遍历都是True，那么说明有效
'''
class Solution:
def checkValidString(self, s: str) -> bool:
def help(a):
cnt = 0
for c in s if a == 1 else reversed(s):
if c == '(': cnt += a
if c == ')': cnt += -a
if c == '*': cnt += 1
if cnt < 0:
return False
return True
return help(1) and help(-1)
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-24 23:29:26
// 贪心
func checkValidString(s string) bool {
minCount, maxCount := 0, 0
for _, ch := range s {
if ch == '(' {
minCount++
maxCount++
} else if ch == ')' {
minCount = max(minCount-1, 0)
maxCount--
if maxCount < 0 {
return false
}
} else {
minCount = max(minCount-1, 0)
maxCount++
}
}
return minCount == 0
}
// stack
func checkValidString2(s string) bool {
var leftStk, asteriskStk []int
for i, ch := range s {
if ch == '(' {
leftStk = append(leftStk, i)
} else if ch == '*' {
asteriskStk = append(asteriskStk, i)
} else if len(leftStk) > 0 {
leftStk = leftStk[:len(leftStk)-1]
} else if len(asteriskStk) > 0 {
asteriskStk = asteriskStk[:len(asteriskStk)-1]
} else {
return false
}
}
i := len(leftStk) - 1
for j := len(asteriskStk) - 1; i >= 0 && j >= 0; i, j = i-1, j-1 {
if leftStk[i] > asteriskStk[j] {
return false
}
}
return i < 0
}
// dp，dp[i][j] 表示字符串 s 从下标 i 到 j 的子串是否为有效的括号字符串
func checkValidString3(s string) bool {
n := len(s)
dp := make([][]bool, n)
for i := range dp {
dp[i] = make([]bool, n)
}
for i, ch := range s {
if ch == '*' {
dp[i][i] = true
}
}
for i := 1; i < n; i++ {
c1, c2 := s[i-1], s[i]
dp[i-1][i] = (c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*')
}
for i := n - 3; i >= 0; i-- {
c1 := s[i]
for j := i + 2; j < n; j++ {
c2 := s[j]
if (c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*') {
dp[i][j] = dp[i+1][j-1]
}
for k := i; k < j && !dp[i][j]; k++ {
dp[i][j] = dp[i][k] && dp[k+1][j]
}
}
}
return dp[0][n-1]
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
java 解法, 执行用时: 9 ms, 内存消耗: 39.8 MB, 提交时间: 2023-09-24 23:27:52
class Solution {
// dp
public boolean checkValidString(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '*') {
dp[i][i] = true;
}
}
for (int i = 1; i < n; i++) {
char c1 = s.charAt(i - 1), c2 = s.charAt(i);
dp[i - 1][i] = (c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*');
}
for (int i = n - 3; i >= 0; i--) {
char c1 = s.charAt(i);
for (int j = i + 2; j < n; j++) {
char c2 = s.charAt(j);
if ((c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*')) {
dp[i][j] = dp[i + 1][j - 1];
}
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];
}
// stack
public boolean checkValidString2(String s) {
Deque<Integer> leftStack = new LinkedList<Integer>();
Deque<Integer> asteriskStack = new LinkedList<Integer>();
int n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '(') {
leftStack.push(i);
} else if (c == '*') {
asteriskStack.push(i);
} else {
if (!leftStack.isEmpty()) {
leftStack.pop();
} else if (!asteriskStack.isEmpty()) {
asteriskStack.pop();
} else {
return false;
}
}
}
while (!leftStack.isEmpty() && !asteriskStack.isEmpty()) {
int leftIndex = leftStack.pop();
int asteriskIndex = asteriskStack.pop();
if (leftIndex > asteriskIndex) {
return false;
}
}
return leftStack.isEmpty();
}
// 贪心
public boolean checkValidString3(String s) {
int minCount = 0, maxCount = 0;
int n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '(') {
minCount++;
maxCount++;
} else if (c == ')') {
minCount = Math.max(minCount - 1, 0);
maxCount--;
if (maxCount < 0) {
return false;
}
} else {
minCount = Math.max(minCount - 1, 0);
maxCount++;
}
}
return minCount == 0;
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 6.4 MB, 提交时间: 2023-09-24 23:26:46
class Solution {
public:
// 贪心
bool checkValidString(string s) {
int minCount = 0, maxCount = 0;
int n = s.size();
for (int i = 0; i < n; i++) {
char c = s[i];
if (c == '(') {
minCount++;
maxCount++;
} else if (c == ')') {
minCount = max(minCount - 1, 0);
maxCount--;
if (maxCount < 0) {
return false;
}
} else {
minCount = max(minCount - 1, 0);
maxCount++;
}
}
return minCount == 0;
}
// 栈
bool checkValidString2(string s) {
stack<int> leftStack;
stack<int> asteriskStack;
int n = s.size();
for (int i = 0; i < n; i++) {
char c = s[i];
if (c == '(') {
leftStack.push(i);
} else if (c == '*') {
asteriskStack.push(i);
} else {
if (!leftStack.empty()) {
leftStack.pop();
} else if (!asteriskStack.empty()) {
asteriskStack.pop();
} else {
return false;
}
}
}
while (!leftStack.empty() && !asteriskStack.empty()) {
int leftIndex = leftStack.top();
leftStack.pop();
int asteriskIndex = asteriskStack.top();
asteriskStack.pop();
if (leftIndex > asteriskIndex) {
return false;
}
}
return leftStack.empty();
}
// dp
bool checkValidString3(string s) {
int n = s.size();
vector<vector<bool>> dp = vector<vector<bool>>(n,vector<bool>(n,false));
for (int i = 0; i < n; i++) {
if (s[i] == '*') {
dp[i][i] = true;
}
}
for (int i = 1; i < n; i++) {
char c1 = s[i - 1];
char c2 = s[i];
dp[i - 1][i] = (c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*');
}
for (int i = n - 3; i >= 0; i--) {
char c1 = s[i];
for (int j = i + 2; j < n; j++) {
char c2 = s[j];
if ((c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*')) {
dp[i][j] = dp[i + 1][j - 1];
}
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];
}
};
javascript 解法, 执行用时: 104 ms, 内存消耗: 43.1 MB, 提交时间: 2023-09-24 23:25:40
/**
* @param {string} s
* @return {boolean}
*/
var checkValidString = function(s) {
const n = s.length;
const dp = new Array(n).fill(0).map(() => new Array(n).fill(false));
for (let i = 0; i < n; i++) {
if (s[i] === '*') {
dp[i][i] = true;
}
}
for (let i = 1; i < n; i++) {
const c1 = s[i - 1], c2 = s[i];
dp[i - 1][i] = (c1 === '(' || c1 === '*') && (c2 === ')' || c2 === '*');
}
for (let i = n - 3; i >= 0; i--) {
const c1 = s[i];
for (let j = i + 2; j < n; j++) {
const c2 = s[j];
if ((c1 === '(' || c1 === '*') && (c2 === ')' || c2 === '*')) {
dp[i][j] = dp[i + 1][j - 1];
}
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];
};
// 栈
var checkValidString2 = function(s) {
const leftStack = [];
const asteriskStack = [];
const n = s.length;
for (let i = 0; i < n; i++) {
const c = s[i];
if (c === '(') {
leftStack.push(i);
} else if (c === '*') {
asteriskStack.push(i);
} else {
if (leftStack.length) {
leftStack.pop();
} else if (asteriskStack.length) {
asteriskStack.pop();
} else {
return false;
}
}
}
while (leftStack.length && asteriskStack.length) {
const leftIndex = leftStack.pop();
const asteriskIndex = asteriskStack.pop();
if (leftIndex > asteriskIndex) {
return false;
}
}
return leftStack.length === 0;
};
// 贪心
var checkValidString3 = function(s) {
let minCount = 0, maxCount = 0;
const n = s.length;
for (let i = 0; i < n; i++) {
const c = s[i];
if (c === '(') {
minCount++;
maxCount++;
} else if (c === ')') {
minCount = Math.max(minCount - 1, 0);
maxCount--;
if (maxCount < 0) {
return false;
}
} else {
minCount = Math.max(minCount - 1, 0);
maxCount++;
}
}
return minCount === 0;
};