题目
给定一个字符串s，判断是不是整体有效的括号字符串。
例如：
- s = ‘()’ -> True
- s = ‘())’ -> False
思路
遍历字符串，记录待匹配的’(‘的个数count，遇到’(’, count += 1，遇到’)’， count -= 1，如果过程中count < 0，返回False。遍历完成，且count恰好为0，返回True
实现
def is_valid(s):
if s is None or len(s) < 2 or len(s) % 2 != 0:
return False
count = 0
for c in s:
if c not in('(', ')'):
return False
if c == ')':
count -= 1
if count < 0:
return False
else:
count += 1
return count == 0
补充题目
给定一个括号字符串，返回最长的有效括号子串长度。
例如：
- ‘(()())’，返回6
- ‘())’, 返回2
- ‘()(()()(’, 返回4
思路
动态规划：
如果s[i] == ‘)’, 令prev = i - dp[i-1] - 1，如果s[prev] == ‘(’，
dp[i] = dp[i-1] + 2
如果prev >= 1:
dp[i] += dp[prev-1]
实现
def max_valid_length(s):
if s is None or len(s) == 0:
return 0
dp = [0] * len(s)
for i in range(1, len(s)):
if s[i] == ')':
prev = i - dp[i-1] - 1
if prev >= 0 and s[prev] == '(':
dp[i] = dp[i-1] + 2 + (dp[prev-1] if prev >= 1 else 0)
return max(dp)
测试
def test_is_valid():
assert(is_valid('') is False)
assert(is_valid('(') is False)
assert(is_valid(')') is False)
assert(is_valid('()') is True)
assert(is_valid('()()') is True)
assert(is_valid('(())') is True)
assert(is_valid('(()())') is True)
assert(is_valid(')((())') is False)
assert(is_valid('())(') is False)
print('pass')
def test_max_valid_length():
assert(max_valid_length('(())') == 4)
assert(max_valid_length('())') == 2)
assert(max_valid_length('(()') == 2)
assert(max_valid_length('(()())') == 6)
assert(max_valid_length('()(()()(') == 4)
print('pass')
if __name__ == '__main__':
test_is_valid()
test_max_valid_length()