根据模式串构造最小数字

难度: Medium

给你下标从 0 开始、长度为 n 的字符串 pattern ，它包含两种字符，'I' 表示上升，'D' 表示下降。

你需要构造一个下标从 0 开始长度为 n + 1 的字符串，且它要满足以下条件：

num 包含数字 '1' 到 '9' ，其中每个数字至多使用一次。
如果 pattern[i] == 'I' ，那么 num[i] < num[i + 1] 。
如果 pattern[i] == 'D' ，那么 num[i] > num[i + 1] 。

请你返回满足上述条件字典序最小的字符串 num。

示例 1：

输入：pattern = "IIIDIDDD"
输出："123549876"
解释：
下标 0 ，1 ，2 和 4 处，我们需要使 num[i] < num[i+1] 。
下标 3 ，5 ，6 和 7 处，我们需要使 num[i] > num[i+1] 。
一些可能的 num 的值为 "245639871" ，"135749862" 和 "123849765" 。
"123549876" 是满足条件最小的数字。
注意，"123414321" 不是可行解因为数字 '1' 使用次数超过 1 次。

示例 2：

输入：pattern = "DDD"
输出："4321"
解释：
一些可能的 num 的值为 "9876" ，"7321" 和 "8742" 。
"4321" 是满足条件最小的数字。

提示：

1 <= pattern.length <= 8
pattern 只包含字符 'I' 和 'D' 。

Submission

运行时间: 24 ms

内存: 15.9 MB

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        cur_num = 2
        ans = [1]
        for p in pattern:
            if p == "I":
                ans.append(cur_num)
            else:
                ans.append(cur_num)
                for i in range(len(ans) - 1, 0, -1):
                    if pattern[i - 1] == "D":
                        temp = ans[i]
                        ans[i] = ans[i - 1]
                        ans[i - 1] = temp
                    else:
                        break

            cur_num += 1
        ans2 = ""
        for num in ans:
            ans2 += str(num)
        return ans2

Explain

该题解采用逐步构建方法，通过遍历模式字符串`pattern`，逐个添加数字到结果列表`ans`中，并根据字符是'I'还是'D'决定如何处理。对于字符'I'，直接在结果列表末尾添加当前数字。对于字符'D'，同样在末尾添加当前数字，然后从当前位置向前遍历，如果前一个字符也是'D'，则将当前数字与前一个数字交换，直到遇到不是'D'的情况或者到达列表开头。最后，将数字列表转换为字符串形式返回。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        cur_num = 2  # 当前要添加到结果中的数字，从2开始
        ans = [1]  # 初始化结果列表，默认开始为1
        for p in pattern:  # 遍历模式串的每个字符
            if p == 'I':
                ans.append(cur_num)  # 如果是'I'，直接添加当前数字
            else:
                ans.append(cur_num)  # 如果是'D'，也添加当前数字
                for i in range(len(ans) - 1, 0, -1):  # 从后向前遍历结果列表
                    if pattern[i - 1] == 'D':
                        # 如果前一个字符是'D'，交换当前和前一个数字
                        temp = ans[i]
                        ans[i] = ans[i - 1]
                        ans[i - 1] = temp
                    else:
                        break
            cur_num += 1  # 更新当前数字
        ans2 = ''
        for num in ans:
            ans2 += str(num)  # 将数字列表转换为字符串
        return ans2

Explore

题解中选择从后向前的单次遍历和交换方法来处理连续的'D'字符，是因为这样可以简化对已放置数字的重新排序。当遇到'D'时，意味着当前数字需要比前一个数字小，所以将新数字放在列表末尾，然后通过交换来确保递减顺序。这个方法在大多数情况下有效，但它依赖于数字的初始和连续放置顺序是正确的。如果初始数字选择不当，或者在某些特殊情况下，比如多次连续'D'后跟'I'，可能需要更复杂的重新排序来确保整个序列的正确性。因此，虽然这种方法在一般情况下能工作，但在某些极端或特殊情况下可能无法生成最优或正确的序列。

是的，算法中使用的交换机制可能会导致在某些特定的pattern输入下生成的数字序列不是最小可能的序列。例如，对于'IDDD'这样的模式，算法从左至右逐渐增加数字，然后通过交换来尝试维持递减顺序，但这种方法可能不会考虑全局最小序列的生成。具体来说，数字的选择和交换只基于局部的模式，没有从全局角度优化数字的分配，因此可能不会生成最小的可行序列。

是的，题解中的算法以1开始，每次递增数字，并没有在算法中明确限制数字的使用范围必须在'1'到'9'之间。因此，在处理较长的pattern字符串时，如果pattern的长度加一（即生成的数字序列的长度）超过9，这种算法将无法继续使用仅1至9的数字来满足题目要求。这种情况下，算法需要进行修改或扩展，以适应长度超过9的输入，可能涉及使用更复杂的数字分配策略或重新设计算法逻辑。