根据模式串构造最小数字

Leetcode Link: 6150. 根据模式串构造最小数字 - 力扣（LeetCode）

题目

解法一

思路： 这题有点难想，我当时做出来的时候是举了很多的例子，并且自己也造了很多的例子。如果在复习的时候也看到了这里，同样需要这样做，为了方便，提前给你几个例子

• “IDDIIIDD”
• “IDIDID”
• “DIIDI”
• “DDDIIIDI”

题目中的关键是”返回字典序最小的结果”，尝试分析上面的例子，我们可以简单得到下面的几个东西

1. 返回结果的数字包含所有[1, n+1]的数字，否则字典序一定不是最小的
2. 返回的结果长度比输入长度多1位
3. 在任意以I结尾的位置，在这之前的结果包含之前的所有数字，比如对于idx = 3的I，此时res[0:4] contain [1,2,3,4], 不考虑顺序（举例: “IIIII??”或者”DDIIII???”这种）
4. 在任意 D 位置的时候，我们需要把当前位置之前的最后一个 I 对应的位置到当前位置的所有位置的结果抬升 1，然后在这个位置上是最后一个值减去 1（举例:“IIDDDII”）

大概是这种感觉, 例子 “IIIDDDII”

题解：

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        res = [1]
        # p 为此位置之前最后一个I的位置，初始化为0，可举例
        p = 0 
        i = 0
        while(i<len(pattern)):
            # 如果遇到D，则需要把p之后到D之前所有位置的结果+1，然后获得此位的结果
            if pattern[i] == 'D':
                for ii in range(p, len(res)):
                    res[ii] += 1
                res.append(res[-1]-1)
            # 如果遇到I，则需要更新p，同时直接获取当前位置的结果
            elif pattern[i] == 'I':
                res.append(res[p]+1)
                p = len(res)-1
            # 记得遍历的位置+1
            i+=1 
        ans = [str(val) for val in res]
        return ''.join(ans)

解法二

思路：一个更为巧妙的解法

我们看上面的例子 大概是这种感觉, 例子 “IIIDDDII”

有点像一个[1:n+1]的数组被部分逆序了！我们只需要考虑在哪里逆序了就行！

举例 pattern = ” I I D D I I” res =“0 1 4 3 2 5 6”

看例子中逆序的那块，其前面最后一个I的idx=1，最后一个D的idx=3。我们res中逆序的部分是位置[2, 4](两边都包含)，即两者+1的关系，至此可以写出代码。

题解：

# digits 是python中预定义的变量， = "0123456789"
# 实际上力扣已经帮忙import了
from string import digits
class Solution:
    def smallestNumber(self, pattern: str) -> str:
        n = len(pattern)
        res = list(digits[1:n+2])
        i = 0
        while(i<len(pattern)):
            if pattern[i] == 'I':
                i += 1
                continue
            # 此之前最后的I的位置，可以是-1，下面会加回来
            p = i-1 
            while(i < len(pattern) and pattern[i] == 'D'):
                i += 1
            # 此时i为最后的D位置+1，因为已经走出了循环。
            res[p+1:i+1] = res[p+1:i+1][::-1] # 对应位置逆序
        
        return "".join(res)
 

启发和联系