移除指定数字得到的最大结果

难度: Easy

给你一个表示某个正整数的字符串 number 和一个字符 digit 。

从 number 中恰好移除一个等于 digit 的字符后，找出并返回按 十进制 表示最大的结果字符串。生成的测试用例满足 digit 在 number 中出现至少一次。

示例 1：

输入：number = "123", digit = "3"
输出："12"
解释："123" 中只有一个 '3' ，在移除 '3' 之后，结果为 "12" 。

示例 2：

输入：number = "1231", digit = "1"
输出："231"
解释：可以移除第一个 '1' 得到 "231" 或者移除第二个 '1' 得到 "123" 。
由于 231 > 123 ，返回 "231" 。

示例 3：

输入：number = "551", digit = "5"
输出："51"
解释：可以从 "551" 中移除第一个或者第二个 '5' 。
两种方案的结果都是 "51" 。

提示：

2 <= number.length <= 100
number 由数字 '1' 到 '9' 组成
digit 是 '1' 到 '9' 中的一个数字
digit 在 number 中出现至少一次

Submission

运行时间: 20 ms

内存: 16.6 MB

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:
        
        max_num = ''
        for i, num in enumerate(number):
            if num == digit:
                max_num = max(max_num, number[:i] + number[i+1:])
        
        return max_num

Explain

该题解通过遍历字符串 `number` 来查找所有等于 `digit` 的字符，每找到一个符合条件的字符，就构造一个新的字符串，该字符串通过移除当前找到的字符得到。然后使用 Python 的内建函数 `max` 来比较并保留当前生成的最大字符串。最终返回的是所有可能生成的字符串中最大的那一个。

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

空间复杂度: O(n)

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:
        # 初始化最大数字字符串为空
        max_num = ''
        # 遍历输入数字的每一个字符
        for i, num in enumerate(number):
            # 检查当前字符是否为待移除的目标字符
            if num == digit:
                # 尝试移除当前字符，生成新的数字字符串，并与已知的最大值比较
                max_num = max(max_num, number[:i] + number[i+1:])
        # 返回所有尝试中找到的最大值
        return max_num

Explore

在这种算法实现中，选择在找到目标数字后立即尝试构造新字符串是因为每次移除一个字符都会生成一个完全不同的数字串，这些数字串相互之间是独立的。算法通过比较所有这些生成的字符串来找出最大的结果。这种方法可以确保考虑到所有可能的移除位置，并通过比较所有这些结果来选择最优解。不需要延迟构造新字符串，因为每个新字符串只依赖于移除特定位置上的字符，而与其他位置的字符无关。

在这个题解中，确实没有直接处理数字前导零的问题。然而，由于输入是一个字符串表示的数字，而且题目可能隐含数字不会以零开头（除非原数字就是零），因此在移除字符后生成的字符串以零开头的情况在此算法中是不考虑的。如果需要处理可能的前导零，可以在生成新字符串后添加一个步骤来剔除这些零，或者在比较时将字符串转换为整数进行比较。

字符串的字典序比较基于字符的Unicode编码顺序，对于纯数字字符串来说，字典序比较确实与数字的数值大小比较一致。这是因为字符'0'到'9'在Unicode编码中是连续且按升序排列的。因此，当比较两个长度相同的数字字符串时，字典序比较和数值大小比较是等效的。但如果长度不同，应确保比较前字符串没有前导零，否则结果可能不正确。在本题中，由于所有生成的字符串长度相同（仅移除一个字符），所以字典序比较适用。

在本题的算法中，每个`digit`的位置都被单独考虑，因此字符的具体位置（无论是开头、中间还是结尾）都会被自动考虑在内。每个可能的移除操作都会生成一个新的字符串，并且所有这些字符串都会参与最终的最大值比较。因此，无需对特定位置的`digit`进行特别处理，因为算法通过枚举所有情况已经包含了这些考虑。