难度: Medium
Submission
运行时间: 28 ms
内存: 16.0 MB
class Solution:
def parseTernary(self, expression: str) -> str:
if len(expression)==1:
return expression[0]
pre,cur,j=1,0,0
for i in range(2,len(expression)):
if expression[i]=='?':
pre+=1
elif expression[i]==':':
cur+=1
if pre==cur:
j=i
break
if expression[0]=='T':
return self.parseTernary(expression[2:j])
else:
return self.parseTernary(expression[j+1:])
Explain
这个题解使用递归的思路来解析给定的三元表达式字符串。主要思路是先判断表达式长度，如果长度为1直接返回该字符。否则从第二个字符开始遍历，记录 '?' 和 ':' 的出现次数，当 '?' 和 ':' 的出现次数相等时，找到了当前三元表达式的中间分隔位置 j。然后根据表达式的第一个字符是 'T' 还是 'F'，递归解析 j 之前的子表达式或 j 之后的子表达式，直到解析到长度为1的子表达式为止。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def parseTernary(self, expression: str) -> str:
if len(expression)==1:
return expression[0]
pre,cur,j=1,0,0
for i in range(2,len(expression)):
if expression[i]=='?':
pre+=1
elif expression[i]==':':
cur+=1
if pre==cur:
j=i # 找到当前三元表达式的中间分隔位置
break
if expression[0]=='T':
return self.parseTernary(expression[2:j]) # 递归解析第一个操作数
else:
return self.parseTernary(expression[j+1:]) # 递归解析第二个操作数
Explore
在题解中，通过计数器 `pre` 和 `cur` 来分别记录 '?' 和 ':' 的出现次数是处理嵌套三元表达式的关键。算法从表达式的第二个字符开始遍历，每遇到一个 '?'，`pre` 的值增加1；每遇到一个 ':'，`cur` 的值增加1。当 `pre` 和 `cur` 的值相等时，意味着遇到的 ':' 正好闭合了之前所有的 '?'，这时的位置标记为 `j`，即为当前要处理的三元表达式的中间分隔位置。这种计数方式确保即使在嵌套的三元表达式中，也能准确地找到每个子表达式的边界。
在高度嵌套的三元表达式中，实际的递归调用栈深度可能接近 n，其中 n 是表达式的总长度。这是因为在最复杂的情况下，每个三元表达式都只包含一个更小的三元表达式（例如 'T?T?F:F:F' 的形式），使得每次递归调用都只能消掉很少的字符。因此，对于高度嵌套的情况，调用栈深度可能逼近 n，而不仅仅是 n/2，这取决于三元表达式的结构。
在当前的实现中，通过严格的计数方式减少了计数错误的可能性。每遇到一个 '?' 和 ':'，计数器分别增加，只有当 '?' 和 ':' 的数量完全匹配时（即 pre == cur），才确定找到了正确的分隔位置 j。这种方法有效地避免了由于计数错误导致的提前或延后找到分隔位置的情况。
题解中并没有明确处理输入格式错误的情况。如果输入的表达式第一个字符不是 'T' 或 'F'，或者该字符缺失，根据当前的代码实现，函数将无法正确工作，并可能导致运行时错误。在实际应用中，应增加错误处理机制，检查输入的表达式是否符合预期的格式，例如在解析前验证表达式的有效性或在代码中添加异常处理逻辑。