最长数字子串（HJ12）

最长数字子串

题目描述

https://www.nowcoder.com/share/jump/5832603751775101880686

对于给定的由数字和小写字母混合构成的字符串 s，找到其中最长的数字子串。如果有多个相同长度的数字子串，则需要全部输出。

• 子串为从原字符串中连续选择一段字符得到的新字符串
• 输入保证至少存在一个数字子串

示例

输入：

abcd12345ed125ss123058789

输出：

123058789,9

输入：

11a22b33c

输出：

112233,2

解题思路

方法一：单次遍历

一次遍历构建带空格的字符串，避免 O(n²) 复杂度。

方法二：正则表达式

使用 re.findall(r'\d+', s) 直接提取所有连续数字串。

代码实现

方法一：单次遍历

s = input().strip()

temp = ""

# 一次遍历：数字直接拼接，非数字加空格（避免重复空格）
for c in s:
    if c.isdigit():
        temp = temp + c
    else:
        if temp and temp[-1] != ' ':
            temp = temp + ' '

arr = temp.split()

# 找最长长度
ans = 0
for d in arr:
    ans = max(ans, len(d))

# 收集所有最长子串
res = ""
for d in arr:
    if len(d) == ans:
        res = res + d

print(str(res) + ',' + str(ans))

方法二：正则表达式

import re

s = input().strip()

# 提取所有连续数字串
arr = re.findall(r'\d+', s)

# 找最长长度
max_len = max(len(x) for x in arr)

# 收集所有最长子串并拼接
res = ''.join(x for x in arr if len(x) == max_len)

print(f"{res},{max_len}")

代码解析

方法一

• 一次遍历构建 temp 字符串：数字直接拼接，非数字加空格
• temp and temp[-1] != ' ' 避免连续空格
• temp.split() 分割得到数字子串列表
• 两个循环：第一个找最长长度，第二个收集所有等于最长长度的子串

方法二

• re.findall(r'\d+', s) - \d+ 匹配一个或多个连续数字
• 列表推导式筛选最长子串
• ''.join() 拼接所有最长子串

时间复杂度

• 方法一：O(n) - 单次遍历
• 方法二：O(n) - 正则表达式线性扫描

注：本题 n ≤ 200，两种方法都能通过

空间复杂度

• O(n) - 存储数字子串列表