Problem:
Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:
- Any left parenthesis
'('
must have a corresponding right parenthesis')'
. - Any right parenthesis
')'
must have a corresponding left parenthesis'('
. - Left parenthesis
'('
must go before the corresponding right parenthesis')'
. '*'
could be treated as a single right parenthesis')'
or a single left parenthesis'('
or an empty string.- An empty string is also valid.
Example 1:
1 2 |
Input: "()" Output: True |
Example 2:
1 2 |
Input: "(*)" Output: True |
Example 3:
1 2 |
Input: "(*))" Output: True |
Note:
- The string size will be in the range [1, 100].
Idea:
Dynamic Programming / Counting
Solution 1:
C++ / DP / Top-down O(n^3)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua // Runtime: 12 ms class Solution { public: bool checkValidString(const string& s) { int l = s.length(); m_ = vector<vector<int>>(l, vector<int>(l, -1)); return isValid(s, 0, l - 1); } private: vector<vector<int>> m_; bool isValid(const string& s, int i, int j) { if (i > j) return true; if (m_[i][j] >= 0) return m_[i][j]; if (i == j) return m_[i][j] = (s[i] == '*'); if ((s[i] == '(' || s[i] == '*') &&(s[j] == ')' || s[j] == '*') && isValid(s, i + 1, j - 1)) return m_[i][j] = 1; for (int p = i; p < j; ++p) if (isValid(s, i, p) && isValid(s, p + 1, j)) return m_[i][j] = 1; return m_[i][j] = 0; } }; |
C++ / DP/ Bottom-up O(n^3)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Author: Huahua // Runtime: 12 ms class Solution { public: bool checkValidString(const string& s) { int l = s.length(); if (l == 0) return true; vector<vector<int>> dp(l, vector<int>(l, 0)); for (int i = 0; i < l; ++i) if (s[i] == '*') dp[i][i] = 1; for (int len = 2; len <= l; ++len) for (int i = 0; i <= l - len; ++i) { int j = i + len - 1; // (...), *...), (...*, *...* if ((s[i] == '(' || s[i] == '*') &&(s[j] == ')' || s[j] == '*')) if (len == 2 || dp[i + 1][j - 1]) { dp[i][j] = 1; continue; } for (int k = i; k < j; ++k) if (dp[i][k] && dp[k + 1][j]) { dp[i][j] = 1; break; } } return dp[0][l - 1]; } }; |
C++ / Counting O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Runtime: 3 ms class Solution { public: bool checkValidString(string s) { int min_op = 0; int max_op = 0; for (char c : s) { if (c == '(') ++min_op; else --min_op; if (c != ')') ++max_op; else --max_op; if (max_op < 0) return false; min_op = max(0, min_op); } return min_op == 0; } }; |
Java / DP / Bottom-up O(n^3)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
class Solution { public boolean checkValidString(String s) { int l = s.length(); if (l == 0) return true; boolean[][] dp = new boolean[l][l]; char[] ss = s.toCharArray(); for (int i = 0; i < l; ++i) if (ss[i] == '*') dp[i][i] = true; for (int len = 2; len <= l; ++len) for (int i = 0; i + len <= l; ++i) { int j = i + len - 1; if ((ss[i] == '*' || ss[i] == '(') &&(ss[j] == '*' || ss[j] == ')')) { if (len == 2 || dp[i + 1][j - 1]) { dp[i][j] = true; continue; } } for (int k = i; k < j; ++k) if (dp[i][k] && dp[k + 1][j]) { dp[i][j] = true; break; } } return dp[0][l - 1]; } } |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment