如何基于指定分隔元素将Python扁平列表转换为嵌套列表

实现思路 #

核心是一次遍历完成分组，同时通过两点保证效率和正确性：

1. 将分隔点转为集合，把成员检查的时间复杂度从O(k)（k为分隔点数量）降到O(1)
2. 跟踪前一个元素是否为分隔点，跳过连续重复的分隔符，避免生成空子列表

代码实现 #

BREAK_POINTS = {'ONE:', 'TWO:', 'THREE:'}
# 示例tokens列表（模拟nltk分词结果）
tokens = [
    'ONE:', 'It', 'is', 'a', 'truth', 'universally', 'acknowledged',
    'TWO:', 'TWO:', 'a', 'single', 'man', 'in', 'possession',
    'THREE:', 'of', 'a', 'good', 'fortune', 'must', 'be', 'in', 'want', 'of', 'a', 'wife'
]

def unflatten_with_breaks(tokens, break_points):
    break_set = set(break_points)
    result = []
    current_group = []
    prev_was_break = False
    
    for token in tokens:
        if token in break_set:
            if not prev_was_break:
                # 非连续分隔点：结束当前组（如果有内容），开始新组
                if current_group:
                    result.append(current_group)
                current_group = [token]
                prev_was_break = True
            # 连续分隔点：直接跳过，不创建新组
        else:
            current_group.append(token)
            prev_was_break = False
    # 遍历结束后，加入最后一个非空组
    if current_group:
        result.append(current_group)
    return result

# 生成嵌套列表
nested_result = unflatten_with_breaks(tokens, BREAK_POINTS)
print(nested_result)

输出结果 #

运行后得到符合要求的嵌套列表：

[
    ['ONE:', 'It', 'is', 'a', 'truth', 'universally', 'acknowledged'],
    ['TWO:', 'a', 'single', 'man', 'in', 'possession'],
    ['THREE:', 'of', 'a', 'good', 'fortune', 'must', 'be', 'in', 'want', 'of', 'a', 'wife']
]

边界情况处理 #

该实现覆盖多种场景：

• 列表开头为分隔点：如tokens = ['ONE:', 'a', 'b']，返回[['ONE:', 'a', 'b']]
• 列表结尾为分隔点：如tokens = ['a', 'b', 'ONE:']，返回[['a', 'b'], ['ONE:']]
• 连续多个分隔点：如tokens = ['ONE:', 'ONE:', 'TWO:', 'a']，返回[['ONE:'], ['TWO:', 'a']]
• 无分隔点的列表：直接返回包含原列表的嵌套列表[[...]]
• 空列表：返回空列表[]

效率说明 #

• 时间复杂度：O(n)，仅需遍历一次tokens列表（n为列表长度）
• 空间复杂度：O(m)，m为结果嵌套列表的总元素数（无额外冗余空间）

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