HJ92 在字符串中找出连续最长的数字串题解

by 限时烟花

抽丝剥茧

本题首先有几个需要关注的地方，容易踩坑。

题目要求输出所有的最长长度的子字符串，而不是一个；
输出的时候所有的符合条件的子字符串之间没有空格

化繁为简

我们首先可以想到，要提取所有的数字子字符串即是要区分数字字符和其他字符。python提供isdigit()函数可以实现字符串是否是数字的判断。故我们的想法可以分为以下几步：

提取所有的数字子字符串；
对子字符串进行进行和长度的判断，找到最长的长度；
对所有最长长度的子字符串进行输出。

2，3两步是比较好解决的，写个循环找到最大值就可以了。那么问题就是第一步中如何提取所有的数字子字符串。

我们可以假设这样一种情况：如果输入的字符串是“ XXXXX XXXXX XXXX XX ”这样的情况，那我们可以很自然地想到使用split()函数进行分割。现在的问题在于数字之间不是空格而是不规则的其他字符。那我们需要做的就是遍历字符串中的所有字符，如果不是数字则取代成空格。这样处理之后就会变成我们所期望的用个隔开数字的格式，此时再采用split进行分割即可。

而面对上一部分提到的问题我们可以使用print()函数的end参数，设置为''来取代默认的'\n'从而完成目标的输出格式。

码上行动

while True:
    try:
        s = input()
        re = ''
        for i in range(len(s)):
            if s[i].isdigit():
                re += s[i]
            else:
                re += ' '
        res = re.split()
        max_len = 0
        longest = None
        for i in res:
            if len(i) > max_len:
                max_len = len(i)
                longest = i
        for i in res:
            if len(i) == max_len:
                print(i, end='')
        print(',' + str(max_len))
    except:
        break

例题图解

alt

心有成算

时间复杂度：由于遍历了输入，故时间复杂度为 $O (n)$
空间复杂度：由于使用常数级别的变量，故空间复杂度为 $O (1)$

另辟蹊径

上述方法是比较取巧的，也可以使用比较朴实如下：

while True:
     
    try:
        sub_str = []
        max_len = 0
        str_input = input()
        for i in range(len(str_input)):
            for j in range(i + 1, len(str_input) + 1):
                if str_input[i: j].isdecimal() and len(str_input[i: j]) >= max_len:
                    sub_str.append(str_input[i: j])
                    max_len = len(str_input[i: j])
        result = ''
        for each in sub_str:
            if len(each) == max_len:
                result += each
        print(result + ',' + str(max_len))
                 
    except:
        break

时间复杂度：由于两层循环，且对子串判断是否为整数，故时间复杂度为 $O (n^{3})$

空间复杂度：不变，仍未 $O (n)$

题解 | #在字符串中找出连续最长的数字串#