查找给定数字字符串中首尾均为1的所有可能数字组合

问题说明 #

给定仅由字符0和1构成的数字字符串，需要从中找出所有以1作为起始字符、同时以1作为结束字符的连续子串。
本次测试用的输入字符串如下：

num_str = '0110101'

参考给出的符合要求的子串示例：

11
1101
101
10101
110101

实现逻辑 #

要找全所有符合要求的子串无需暴力遍历所有可能子串，按以下步骤实现效率更高：

• 先遍历一遍原字符串，把所有字符为'1'的索引位置按顺序存到列表里，对于输入'0110101'，所有1的索引位置是[1,2,4,6]（索引从0开始计数）
• 所有首尾都是1的连续子串，本质就是取上述列表中任意两个位置，靠前的作为子串起点、靠后的作为子串终点，截取两个索引之间（包含两端）的字符串即可
• 如果要求子串长度至少为2，就取两个不同的索引（起点<终点）；如果允许单个字符'1'也算符合要求，就把同一个索引的情况也加进去

可直接运行的Python代码 #

num_str = '0110101'
# 收集所有1所在的索引
one_indexes = [i for i, c in enumerate(num_str) if c == '1']
res = []
# 遍历所有起点、终点组合
for start_idx in range(len(one_indexes)):
    # 长度≥2的情况，终点从起点的下一个位置开始取
    for end_idx in range(start_idx + 1, len(one_indexes)):
        s = one_indexes[start_idx]
        e = one_indexes[end_idx]
        res.append(num_str[s:e+1])

# 打印所有结果
for item in res:
    print(item)

运行结果 #

执行上述代码后，得到的所有长度≥2、首尾为1的连续子串如下：

11
1101
110101
101
10101
101

注：给出的参考示例共列了5个符合要求的子串，遗漏了索引4到6位置对应的101，该子串同样满足首尾为1的要求。

内容的提问来源于stack exchange，提问作者Roshankumar