【问题】使用Python将字符串过滤并保留关键字
Post

【问题】使用Python将字符串过滤并保留关键字

Python 算法备忘。

问题描述

给出一个关键词列表:

1
keys = ['aaa','bbb','ccc']

给出一个字符串 str,如果字符串中有包含列表 keys 中的子串,则过滤并保留下来,其余部分则删除。请问可以如何实现?

例子:

1
str = 'aaaawtf he heheccc'

过滤后变成:

1
'aaa ccc'

例子二:

1
str = 'aaabbb/&edfg cccaaa'

过滤后变成:

1
'aaabbb cccaaa'

要求尽可能保留原字符串的相对位置信息,比如aaa和bbb是连在一块的,就连在一块被保留下来。

实现思路

解决这个问题可以分两步走,第一步,找出关键字位置并记录;第二步,重新组合拼接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
str = 'aaabbb/&edfg cccaaa'
keys = ['aaa', 'bbb', 'ccc']

found = {k: [] for k in keys}
total_length = len(str)

# 按key依次遍历字符串,保存出现的位置
for key in keys:
    length, i = len(key), 0

    while i + length <= total_length:
        s = str[i:i + length]

        if s == key:
            found[key].append(i)
            i += length
        else:
            i += 1

print(found)
# {'aaa': [0, 16], 'bbb': [3], 'ccc': [13]}

result, next_match_index = '', -1

# 重新组合,如果坐标重叠连接符为空,否则为空格
for i in range(total_length):
    for k, v in found.items():
        if i in v:
            split = '' if next_match_index == i else ' '

            result = result + split + k
            next_match_index = i + len(k)

print(result)
# aaabbb cccaaa

改进方案

其实可以考虑以上两步可以合并一起做掉,不过代码就相对没那么好理解了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
str = 'aaaabbb/&edfg cccaaa'
keys = ['aaa', 'bbb', 'ccc']

total_length = len(str)
result, next_match_index, skip = '', -1, 0

for i in range(total_length):

    if skip:
        skip -= 1
        continue

    for key in keys:  # 查找当前位置是否有match的key
        length = len(key)

        if i + length <= total_length:  # 确保index不越界
            s = str[i:i + length]

            if s == key:  # 如果有match的key,添加到结果
                split = '' if next_match_index == i else ' '
                result = result + split + key

                next_match_index = i + length #预测相邻key的位置
                skip = length - 1 #需要跳过当前key后匹配下一个key
                break # 已经找到匹配key,可以结束keys的遍历

print(result)

【问题】从一长串数字中找到重复多次的三个数字

识别图片中的文字 - Tesseract 和 百度云OCR的对比