题目重点：将星号明确为左括号、右括号或空，线性判定，并用DFS枚举去重后结果。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练只含(、)、*，每个*独立替换为(、)或空串；只输出合法括号串，不输出替换决策历史。
- 空输入合法，枚举得到包含空字符串的列表；输出不同字符串去重并排序。
- 枚举与判定复杂度分别说明，星号很多时输出可指数增长。
解题路线
- 标准括号余额balance是左数减右数，任何前缀不能负，最终必须0。有*时同一前缀可对应多个余额；只保存最小low和最大high，描述仍可达到的非负余额区间。
- 遇(两端加1；遇)两端减1，但low截为0；遇*，最小可少1（当作右）且不能负，最大可多1（当作左）。因为*还可为空，每步可达余额不会形成奇偶空洞，区间表示完整。
- 若high<0，所有替换都已出现负前缀，立即False；末尾low=0表示至少有一条路线回到零。只看总括号数或把所有*优先补左括号，会忽略前缀约束。
- 枚举时DFS维护index、实际balance与字符前缀。*依次试空、左、右；负余额立即剪枝，balance>剩余字符数时即使余下全右也无法归零，同样剪枝。
- 到末尾balance=0才加入结果集合。不同替换历史可能产生同一字符串，例如两个*可以左右或空空等不同路径，输出合同要求按最终字符串去重，而不是把每条决策都算独立答案。
- 不要把线性判定算法说成能在线性时间输出全部答案。判定只证明存在；枚举必须承担输出大小，prefix列表追加/弹出避免每层反复复制长字符串，叶子再join。
- 若*只允许左右而不能空，可达余额具有奇偶限制，本文low截零的连续区间论证需调整。若追问输出一种可行替换，可记录构造而非枚举所有，先重新确认空替换的规则。
手动走一遍
(*)可把*当空得到()；(*))把*当左得到(())；)*无论如何开头已负，False。输入**的不同合法结果是空串和()；多个替换路线输出同一串时只留一份。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def valid_star(text):
if any(c not in '()*' for c in text):
raise ValueError('expected parentheses or star')
low = high = 0
for char in text:
if char == '(':
low += 1
high += 1
elif char == ')':
low = max(0, low - 1)
high -= 1
else:
low = max(0, low - 1)
high += 1
if high < 0:
return False
return low == 0
def expand_valid(text):
if any(c not in '()*' for c in text):
raise ValueError('expected parentheses or star')
results, prefix = set(), []
def search(index, balance):
if balance < 0 or balance > len(text) - index:
return
if index == len(text):
if balance == 0:
results.add(''.join(prefix))
return
choices = ('', '(', ')') if text[index] == '*' else (text[index],)
for char in choices:
if char:
prefix.append(char)
search(index + 1, balance + (char == '(') - (char == ')'))
if char:
prefix.pop()
search(0, 0)
return sorted(results)
复杂度
判定O(n)时间O(1)工作空间。枚举有s个星号，粗界O(n·3^s)时间，DFS工作O(n)；S个不同答案总字符量O(Sn)，排序另计O(S log S·n)。递归深度n。
易错点与追问
容易失分的边界
- 只检查最终余额忽略负前缀。
- 星号不允许空却使用本文区间论证。
- 枚举重复串未去重。
- 将指数输出写成线性时间。
继续深挖
- 只要一组合法替换怎么构造？
- 替换历史数和不同结果数为何不同？
- 若*不允许空如何加入奇偶约束？
- 只计答案是否能用DP而不保存字符串？
