难度: Medium
Submission
运行时间: 33 ms
内存: 17.0 MB
class Solution:
def findPermutation(self, s: str) -> List[int]:
res, x = [], 1
for sub in s.split('I'):
res.extend(range(x+len(sub), x-1, -1))
x += len(sub)+1
return res
Explain
这个题解的思路是通过拆分字符串 s，将其分成多个子字符串，每个子字符串以 'I' 为分隔。对于每个子字符串，生成一个降序的数字序列，序列的起始值为当前的 x 值加上子字符串的长度，终止值为 x。最后将所有生成的数字序列合并到结果列表中。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def findPermutation(self, s: str) -> List[int]:
res, x = [], 1
for sub in s.split('I'): # 将字符串 s 按照 'I' 拆分成子字符串
# 对于每个子字符串，生成一个降序的数字序列
# 序列的起始值为 x + 子字符串的长度，终止值为 x
res.extend(range(x+len(sub), x-1, -1))
x += len(sub)+1 # 更新 x 的值，为下一个子字符串做准备
return res # 返回最终的排列结果
Explore
在这个问题中，字符串s由字符'I'和'D'组成，分别代表下一个数字应该比前一个数字大（递增）或小（递减）。使用'I'作为分隔符是因为每次遇到'I'，都表示一个新的递增序列的开始。也就是说，'I'自然地将字符串分割为若干部分，每部分都是一个连续的递减序列（即D序列），使得每个部分都可以独立处理并生成降序数字序列。这种方法直接利用了字符串的性质来简化问题解决方案的实现。
选择起始值为x加上子字符串的长度是为了确保序列的数字能够正确地递减，并且与前面的数字序列连接时满足题目要求的大小关系。具体来说，x是当前子序列的起始数字，加上子字符串的长度意味着从当前位置起，考虑后续的'D'数量，确保生成的数字序列在连接前一个序列时能保持整体的递减顺序。这样做能确保每个数字都是唯一的，并且按照题目要求的顺序递减排列。
在更新x的值时，将长度加1是为了包含分隔字符'I'后的第一个递增位置。每次处理完一个子字符串后，x需要指向下一个新的子序列的起始数字。由于子字符串是以'I'结尾分割的，所以x的更新需要包括所有D字符的数量加上一个额外的1来跳过'I'本身，确保每个新的数字序列都从正确的位置开始。
在没有'I'的情况下，整个字符串s可以被视为一个单独的子字符串。由于没有'I'作为分隔，这意味着整个序列应该是降序的。因此，可以直接从n（字符串长度加1）开始递减到1生成整个数字序列。这种情况下，起始值x为1，长度为s的长度，所以生成的序列将是从x+s长度即n开始，递减到x即1的序列。