子字符串突变后可能得到的最大整数

难度: Medium

给你一个字符串 num ，该字符串表示一个大整数。另给你一个长度为 10 且 下标从 0 开始 的整数数组 change ，该数组将 0-9 中的每个数字映射到另一个数字。更规范的说法是，数字 d 映射为数字 change[d] 。

你可以选择突变 num 的任一子字符串。突变子字符串意味着将每位数字 num[i] 替换为该数字在 change 中的映射（也就是说，将 num[i] 替换为 change[num[i]]）。

请你找出在对 num 的任一子字符串执行突变操作（也可以不执行）后，可能得到的 最大整数 ，并用字符串表示返回。

子字符串 是字符串中的一个连续序列。

示例 1：

输入：num = "132", change = [9,8,5,0,3,6,4,2,6,8]
输出："832"
解释：替换子字符串 "1"：
- 1 映射为 change[1] = 8 。
因此 "132" 变为 "832" 。
"832" 是可以构造的最大整数，所以返回它的字符串表示。

示例 2：

输入：num = "021", change = [9,4,3,5,7,2,1,9,0,6]
输出："934"
解释：替换子字符串 "021"：
- 0 映射为 change[0] = 9 。
- 2 映射为 change[2] = 3 。
- 1 映射为 change[1] = 4 。
因此，"021" 变为 "934" 。
"934" 是可以构造的最大整数，所以返回它的字符串表示。

示例 3：

输入：num = "5", change = [1,4,7,5,3,2,5,6,9,4]
输出："5"
解释："5" 已经是可以构造的最大整数，所以返回它的字符串表示。

提示：

1 <= num.length <= 10⁵
num 仅由数字 0-9 组成
change.length == 10
0 <= change[d] <= 9

Submission

运行时间: 72 ms

内存: 18.0 MB

class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        # 只保留会变大的操作
        mapping = {str(i):str(x) for i, x in enumerate(change) if x >= i}
        # 定位到可以突变的连续子字符串
        num = list(num)
        n, i = len(num), 0
        while i < n and (num[i] not in mapping or mapping[num[i]] == num[i]):
                i += 1
        if i < n:
            j = i
            while j < n and num[j] in mapping:
                num[j] = mapping[num[j]]
                j += 1
        return ''.join(num)

Explain

本题解的思路是首先创建一个字典 `mapping`，其中只包含那些通过变换可以使得数字变大或保持不变的映射关系。然后，将数字字符串 `num` 转换成列表以便于修改。接着，搜索字符串的第一个可以开始突变的位置，即找到第一个在 `mapping` 中的数字，且映射后的数字不小于原数字。从这个位置开始，对后续的数字进行替换，直到遇到一个数字不在 `mapping` 中，或者替换后的数字小于原数字，此时停止替换。最后，将列表转换回字符串形式，得到最终结果。

时间复杂度: O(n)

空间复杂度: O(n)

# 解题类定义
class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        # 创建一个字典，只包含可以使数字不减小的映射关系
        mapping = {str(i): str(x) for i, x in enumerate(change) if x >= i}
        # 将字符串转换为列表以便修改
        num = list(num)
        n, i = len(num), 0
        # 查找第一个可以突变的位置
        while i < n and (num[i] not in mapping or mapping[num[i]] == num[i]):
            i += 1
        # 从找到的位置开始，进行突变，直到不可能再突变为止
        if i < n:
            j = i
            while j < n and num[j] in mapping:
                num[j] = mapping[num[j]]
                j += 1
        # 将列表转换回字符串形式
        return ''.join(num)

Explore

在这个问题中，我们的目标是通过数字的突变来获得尽可能大的整数。因此，只选择映射后的数字不小于原数字的映射关系，是为了确保每次突变都不会减少数字的值，从而有助于达到或保持当前的最大可能值。理论上，减小某个数字可能在某些特定情况下通过触发更高位的变化来获得更大的整数，但这种情况非常特殊且难以直接通过一次映射来实现。因此，本题解采用的策略是简单且直接的，即只进行非减少的映射，以保证结果总是趋向于更大的整数值。

这种策略的选择是为了保留数字的高位优先级，因为数字的最高位对整体值的影响最大。一旦开始替换，如果遇到一个数字不在映射中或者替换后的数字小于原数字，则继续替换可能会导致整体数字减小。此外，跳过某个不可突变的数字继续替换更低位的数字，虽然理论上可行，但实际上对整体数字的影响较小，因此可能不值得复杂化算法。

创建字典`mapping`时包括了映射后的数字大于或等于原数字的情况。如果原数字与映射数字相等，这意味着突变操作可以保持该数字不变，而不是降低其值。这有助于在保持当前数字不变的同时，探查后续的数字是否可以提升，从而可能实现整体数字的增加。包含这种情况，使得算法在实现上更加简洁，并且能够适应不同的输入情况，保证算法的通用性和灵活性。

如果在遍历`num`字符串的过程中发现所有数字都不在`mapping`中，或者所有可替换的数字替换后与原数字相等，这意味着没有任何突变可以执行，或者突变不会改变当前数字的值。在这种情况下，算法应当直接返回原始数字字符串，因为没有任何变化可以产生更大的数值。这种处理方式确保了算法的效率和正确性，避免了不必要的操作。