Enumerating k-mers Lexicographically

Organizing Stringsclick to collapse

When cataloguing a collection of genetic strings, we should have an established system by which to organize them. The standard method is to organize strings as they would appear in a dictionary, so that “APPLE” precedes “APRON”, which in turn comes before “ARMOR”.

Problem
Assume that an alphabet A has a predetermined order; that is, we write the alphabet as a permutation A=(a1,a2,…,ak) where a1Given two strings s and t having the same length nn, we say that s precedes t in the lexicographic order (and write s<Lext) if the first symbol s[j] that doesn’t match t[j] satisfies sjGiven: A collection of at most 10 symbols defining an ordered alphabet, and a positive integer nn (n≤10).
Return: All strings of length nn that can be formed from the alphabet, ordered lexicographically (use the standard order of symbols in the English alphabet).
Sample Dataset
A C G T
2
Sample Output
AA
AC
AG
AT
CA
CC
CG
CT
GA
GC
GG
GT
TA
TC
TG
TT

解题思路：可重复组合

本题其实就是给定 n 种字符，每个字符可以使用无限次，按 字典序 输出组合。由于本题输入序列已经排序，因此对于每个根（输入序列个数），其树的高度不超过 2 的前序遍历结果就是答案。
字典序可重复组合.drawio

from typing import List
class Solution:
    def combine(self, s: str, k: int) -> List[str]:
        res = []
        path = []
        def backtrace(idx: int) -> None:
            """回溯函数：每个字符 s[idx] 可以和其后 [idx+1, n) 中选择 n-1 个构成组合"""
            if k == len(path):  # 达到 k 个组合，加入答案中
                res.append(''.join(path))  # 此处必须拷贝，否则传引用是同一份 path
                return  # 不准继续添加
            for j in range(len(s)):  # [idx, n) 表示可重复选择
                path.append(s[j])  # 选择当前 s[j]
                backtrace(j + 1)  # 下一个字符在 [j+1,n) 选
                path.pop()
        backtrace(0)
        return res
seqs = input().split()  # 输出序列
k = int(input())  # 转为整数
for s in Solution().combine(seqs, k):
    print(s)

复杂度分析：

• 时间复杂度：，每个节点有 n 种选择（包含自身），树的高度为 k 。如本题一共有 种组合。
• 空间复杂度：