284模板串匹配问题

题解

本题要求在给定的“模板串”中，替换所有的 '?' 以构造出多个不含前导零的正整数，并找出按字典序排列后的第 k 小的数。如果不存在满足条件的第 k 小数，返回 -1。

解题思路

1. 前导零检查：

   • 首先检查模板串的首字符是否为 '0'，如果是'0'，则直接返回 -1，

2. 从后向前替换 '?'：

   • 假如不考律前导 0 的情况，??? 每个?都有十种可选的数字，可以替换为 000 到 999，共 1000 种可能。第 k 小的数，即为第 k - 1 个数。并且每个位置的”?“填入的正应该是k - 1的十进制的每一位数字
   • 对于从后往前的每一个 '?'，用 k % 10 来替换该位置的字符，并将 k 整除以 10，以便为下一个 '?' 的替换提供新的数字。

3. 处理首位 '?'：

   • 如果首位是 '?'，则需要特别处理：
     • 替换为 k + 1，确保首位不是 '0'。
     • 检查 k + 1 是否小于 10，否则无法替换为单个数字，返回 -1。

代码解析

def solution(s: str, k: int) -> str:
    s = list(s)
    if s[0] == "0":
        return "-1"
    k -= 1
    for i in range(len(s) - 1, 0, -1):
        if s[i] == "?":
            s[i] = str(k % 10)
            k //= 10
    # 处理首位是 '?' 的情况
    if s[0] == "?" and k + 1 < 10:
        s[0] = str(k + 1)
        k = 0
    # 如果 k 不等于 0，说明没有找到第 k 小的数
    return "".join(s) if k == 0 else "-1"

复杂度分析

• 时间复杂度：O(n)，其中 n 是模板串的长度。需要遍历字符串一次进行替换。
• 空间复杂度：O(n)，用于存储字符串的列表形式。