1. 问题引入当“设计密码”成为一个算法问题最近在刷LeetCode时遇到了一个很有意思的题目编号1052标题叫“设计密码”。乍一看我以为是关于密码学或者安全策略的设计心里还琢磨着是不是要搞什么哈希、盐值或者加密算法。但点进去一看才发现完全不是那么回事。这其实是一道结合了字符串匹配和动态规划的经典题目其核心是给定一个字符串S作为“密码”的模板以及一个“不良”字符串T要求你设计一个长度为N的密码这个密码不能包含子串T。同时密码的每一位都必须从S的字符集中选取。问一共有多少种不同的设计方式。这个题目之所以吸引我是因为它把“设计”这个看似开放性的概念转化为了一个非常精确的计数问题。它考察的不是你的创意而是你对自动机理论和动态规划状态设计的深刻理解。在实际的软件开发中这种思想无处不在比如在内容过滤系统确保用户输入不包含敏感词、基因序列分析避免特定有害序列、甚至是一些游戏内的命名规则校验中你都会遇到类似的“在约束下计数”的问题。今天我就来详细拆解这道题不仅给出解法更会深入探讨其背后的KMPKnuth-Morris-Pratt算法原理以及如何将其状态机模型完美地融入到动态规划的递推关系中。你会发现这不仅仅是一道题更是一个理解复杂状态转移的绝佳案例。2. 核心问题拆解与抽象建模首先我们必须把题目描述翻译成程序员能理解的语言。题目通常是这样给的给定一个长度为M的字符串S它定义了密码可以使用的字符集合注意S可能包含重复字符但集合意义是字符池。给定一个长度为L的“不良”字符串T。我们需要构造一个长度为N的新字符串P即密码。P的每个字符都必须来自S中的字符。P中不能出现子串T。我们需要计算所有满足条件的P的数量结果通常对一个很大的数如1e97取模。这里有几个关键点需要立刻厘清字符来源S是字符池。例如S “abc”那么密码的每一位只能是 ‘a‘, ‘b‘, 或 ‘c‘。题目没有明说S是否包含所有可打印字符但根据常见变体我们通常认为S是一个给定的、可能包含重复的字符串我们从中依次选取字符。更精确的理解是构造密码时对于第i位我们可以独立地选择S中的任何一个字符。因此如果S的长度为M那么在不考虑禁忌串T的情况下总方案数是M^N。我们的任务就是从这M^N种方案中剔除那些包含了子串T的“坏”方案。禁止子串不能出现子串T意味着一旦在构造P的过程中我们拼出的某个后缀与T完全匹配那么这个构造过程就立刻失败了。这提示我们需要在构造过程中时刻跟踪当前已构造部分的后缀与T的匹配程度。计数与取模由于N可能很大比如 1000 5000M^N是一个天文数字我们必须使用动态规划来避免指数爆炸并且要对结果取模这是处理大数计数问题的标准操作。所以问题的核心模型就变成了我们如何在一个线性的构造过程中一位一位地添加字符动态地记录并规避“形成完整禁忌串T”这一事件一个最朴素的想法是我们定义dp[i]为构造了前i位密码且不包含T的方案数。但这样定义无法进行状态转移因为当我们决定第i1位的字符时我们无法知道当前字符串的后缀是什么从而无法判断新增这个字符后是否会形成T。这就引出了我们需要记录的关键状态当前已构造字符串的后缀与禁忌串T的匹配长度。3. KMP状态机将匹配过程转化为状态转移图为了高效地处理“当前后缀与T的匹配情况”我们需要请出字符串匹配领域的王牌算法——KMP算法。KMP的核心在于一个next数组或称fail数组、部分匹配表它记录了模式串T的真前缀和真后缀的最长公共长度。这里我们简单回顾一下next数组的定义和构建过程这对于理解后续的状态机至关重要 对于模式串T(长度为L)我们定义next[j](0 j L) 表示子串T[0:j]即T的前 j1 个字符中其真前缀不包括自身和真后缀的最长公共长度。通常我们令next[0] -1或0作为边界条件。构建算法是线性的 O(L)。例如对于T “ababc”:j0,T[0:0]“a“, 没有真前缀/后缀next[0] -1。j1,T[0:1]“ab“, 真前缀有 {“a“}真后缀有 {“b“}无公共next[1] 0(有时表示为回退到索引0但公共长度为0)。j2,T[0:2]“aba“, 真前缀 {“a“, “ab“}真后缀 {“ba“, “a“}公共最长串为 “a“长度1所以next[2] 1。j3,T[0:3]“abab“, 真前缀 {“a“, “ab“, “aba“}真后缀 {“bab“, “ab“, “b“}公共最长串为 “ab“长度2next[3] 2。j4,T[0:4]“ababc“, 真前缀 {“a“, “ab“, “aba“, “abab“}真后缀 {“babc“, “abc“, “bc“, “c“}无公共next[4] 0。next数组的精妙之处在于当我们在文本串中匹配T失败时假设在T[j]处失败我们不需要将文本串的指针完全回退而是可以将T的匹配指针j回退到next[j]的位置继续尝试匹配。这本质上构建了一个确定有限状态自动机DFA。对于本题我们可以这样构建状态机状态我们用j(0 j L) 来表示当前已构造的密码字符串的后缀与禁忌串T匹配的长度。也就是说j意味着我们下一个将要尝试匹配的T的字符索引是T[j]。初始状态j 0表示尚未开始匹配任何T的字符。接受状态危险状态j L。一旦到达这个状态意味着我们已经完整匹配了T即密码中出现了禁忌子串。这是我们绝对要避免的状态。转移假设当前状态是j我们新添加一个字符c。转移过程模拟了KMP的匹配过程如果c T[j]那么匹配长度可以增加1状态转移到j1。如果c ! T[j]那么我们需要利用next数组进行回退。我们不断地令j next[j]直到j回退到 -1根据实现或者找到一个j‘使得c T[j‘]。如果回退到 -1意味着当前字符c与T的开头都不匹配那么新的匹配长度就是0即状态转移到0然后看c是否等于T[0]来决定下一步。在实际状态机实现中我们会预处理一个转移矩阵trans[j][c]它直接给出了从状态j遇到字符c后下一个状态k是什么。这个预处理过程就运用了KMP的next数组。通过这样的建模我们将“构造密码”的过程转化为了在这个KMP状态机上的行走。我们从状态0出发每添加一个字符就根据该字符进行一次状态转移。我们的目标是走N步即构造长度为N的密码并且途中永远不能踏入状态L。注意这里有一个非常重要的细节。状态L是一个“吸收态”或“非法态”。一旦进入状态L无论后续添加什么字符这个密码都已经包含了T是无效的。在我们的动态规划中我们会确保不从这个状态进行任何转移或者将其方案数始终记为0。4. 动态规划递推将状态机转化为计数方程有了KMP状态机动态规划的方程就呼之欲出了。我们定义动态规划数组dp[i][j]i表示我们已经构造了密码的前i位 (0 i N)。j表示在构造完前i位后我们所处的KMP状态机状态 (0 j L)。j的含义是当前字符串后缀与T的最长匹配长度。dp[i][j]的值表示构造长度为i的密码且最终处于状态j即不包含完整T且匹配长度为j的所有合法方案数。初始状态dp[0][0] 1。构造了0位密码匹配长度自然为0只有1种方案空串。对于其他jdp[0][j] 0。状态转移 假设我们已经计算好了dp[i][j]现在要添加第i1位字符。对于每个可选的字符c来自字符串S我们根据预处理好的转移矩阵trans[j][c]计算出添加字符c后会转移到的新状态k。关键限制如果k L说明添加字符c后形成了完整的T这个转移是禁止的。因此我们只考虑k L的转移。对于所有合法的转移k L我们将dp[i][j]的方案数累加到dp[i1][k]上。用伪代码表示转移方程就是对于 i 从 0 到 N-1 对于 j 从 0 到 L-1 如果 dp[i][j] 0 对于 S 中的每一个字符 c k trans[j][c] 如果 k L: # 确保不形成完整T dp[i1][k] dp[i][j] dp[i1][k] % MOD其中MOD是取模数如1e97。最终答案 当我们构造完N位密码后 (i N)所有不包含T的合法方案其最终状态j可以是 0 到 L-1 中的任何一个。因此答案是ans sum(dp[N][j] for j in range(0, L)) % MOD这个动态规划的时间复杂度是O(N * L * M)其中M是字符集S的大小或理解为字符种类数。空间复杂度可以是O(N * L)通过滚动数组优化到O(L)。5. 预处理转移矩阵KMP Next数组的实战应用动态规划的核心依赖于转移矩阵trans[j][c]。如何高效地预处理它这里就是KMPnext数组大显身手的地方。我们不是对每个(j, c)都去模拟匹配过程而是利用next数组进行“快速跳转”。假设字符集的大小为C比如小写字母是26S中出现的所有字符去重后的数量。我们目标是构建一个大小为L x C的矩阵trans。算法步骤计算模式串T的next数组长度为L。通常实现中next[0] -1。初始化trans矩阵。对于每个状态j(0 j L) 和每个字符c如果c T[j]那么显然匹配成功trans[j][c] j 1。如果c ! T[j]那么我们需要找到一个新的状态k使得T[0:k]是T[0:j] c这个新字符串的后缀。这正好是KMP匹配失败时的回退过程。我们可以用以下循环计算k next[j] while k 0 and T[k] ! c: k next[k] trans[j][c] k 1 # 因为回退后匹配了一个字符或者回退到-1后从0开始匹配注意当k -1时k1 0表示匹配长度归零。有一个更高效的预处理方法可以避免对每个(j, c)都进行while循环。我们可以利用动态规划的思想按j从 0 到 L-1 的顺序计算对于j 0如果c T[0],trans[0][c] 1否则trans[0][c] 0。对于j 0我们可以利用已经计算好的trans[next[j]]来加速。因为对于c ! T[j]的情况其转移结果应该和从状态next[j]遇到字符c的转移结果相同除了匹配成功的那个字符。但为了清晰和避免出错许多实现中仍然使用上述循环方法因为L和C通常不会太大L最多几十C为26或52这个预处理的代价是可以接受的。这里给出一个Python风格的预处理函数示例def build_transition(T, charset): L len(T) # 1. 构建next数组 next_arr [-1] * (L 1) # 多一位方便处理 i, j 0, -1 while i L: while j 0 and T[i] ! T[j]: j next_arr[j] i 1 j 1 next_arr[i] j # 2. 构建转移矩阵 trans[j][c] - next_state # 先将字符映射到索引 char_to_idx {ch: idx for idx, ch in enumerate(charset)} C len(charset) trans [[0] * C for _ in range(L 1)] # 状态包含0到LL是非法态 for state in range(L 1): # 注意这里state可以到L for ch_idx, ch in enumerate(charset): if state L and ch T[state]: # 匹配成功转移到下一个状态 trans[state][ch_idx] state 1 else: if state 0: # 状态0匹配失败只能回到状态0除非chT[0]但上面判断了不等于 trans[state][ch_idx] 0 else: # 利用next数组回退 # next_state next_arr[state] 是回退后的状态 # 然后看从这个回退状态遇到字符ch会转到哪里 # 注意这里直接使用 trans[next_arr[state]][ch_idx] 需要确保该值已计算 # 由于我们按state从小到大计算而 next_arr[state] state所以是安全的 trans[state][ch_idx] trans[next_arr[state]][ch_idx] return trans, next_arr注意在这个实现中trans矩阵的大小是(L1) x C包含了非法状态L。在动态规划时我们只使用state L的部分进行转移并且要确保不从状态L转移出去或者直接不计算dp[i][L]。6. 边界条件、取模与复杂度优化在实现动态规划时有几个细节必须处理好否则极易出错。1. 取模运算 由于方案数可能极其巨大必须在每次加法后立即取模。通常模数MOD 10**9 7。在Python中使用% MOD即可。在C/Java中需要注意使用long long类型并在相加后取模防止溢出。2. 滚动数组优化 我们的状态转移方程dp[i1][k] dp[i][j]只依赖于上一行i。因此我们可以将dp数组从[N1][L]优化为两个一维数组cur[L]和nxt[L]交替使用。这样空间复杂度从 O(N*L) 降为 O(L)对于较大的N如 10^5是必要的。 优化后的伪代码cur [0] * L cur[0] 1 # dp[0][0] 1 for i in range(N): nxt [0] * L for j in range(L): if cur[j] 0: continue for c in S_chars: # 遍历字符集S中的每个字符 k trans[j][c] if k L: nxt[k] (nxt[k] cur[j]) % MOD cur nxt ans sum(cur) % MOD3. 字符集的处理 题目中的S是一个字符串它定义了每位密码可选的字符。注意S中可能有重复字符。在动态规划转移时我们需要遍历S中的每一个字符而不是遍历去重后的字符集。因为即使字符相同它们也被视为不同的选择如果题目明确说明S是字符集则去重但通常LeetCode 1052题描述中S是作为“模板字符串”每位独立选择重复字符意味着该字符被选中的概率或次数更多在计数时需要重复计算。这一点至关重要也是常见的坑点。例如S “aa“那么对于每一位你有两个‘a‘可以选择虽然它们看起来一样但在计数时是两种不同的选择方案。因此在转移循环中我们直接遍历字符串S的每个字符即可。4. 初始状态与答案 初始时dp[0][0] 1其他为0。最终答案是所有dp[N][j](0 j L) 的和。为什么不包括j L因为j L表示构成了完整的T是非法状态其方案数始终为0如果我们没有从它转移出去的话。5. 时间复杂度分析预处理trans矩阵O(L * C)其中 C 是字符集大小S中去重后的字符数。通常 C 26 或 52。动态规划O(N * L * M)其中 M 是字符串S的长度注意不是去重后的C。因为内层循环需要遍历S的每个字符。 如果M很大比如S很长这个复杂度可能偏高。但通常题目中N和L是主要约束M较小。如果M很大我们可以进行优化因为S中可能有大量重复字符我们可以先统计每个字符出现的次数然后对于每个状态j一次性加上count[ch] * dp[i][j]到nxt[trans[j][ch]]。这样复杂度可以降为 O(N * L * C)其中 C 是字符种类数。这是性能优化的关键点也是面试中可能被追问的地方。7. 从理论到实践完整代码实现与测试结合以上所有分析我们可以给出一个健壮的、经过优化的Python实现。这里我们采用统计字符频率的方法来优化转移。MOD 10**9 7 class Solution: def designPassword(self, N: int, S: str, T: str) - int: M len(S) L len(T) if L 0: return 0 # 禁忌串为空无法构造任何密码或者根据题意可能返回0 if N L: # 密码长度小于禁忌串长度肯定不包含T答案是 M^N return pow(M, N, MOD) # 1. 预处理字符频率 from collections import Counter freq Counter(S) # 统计S中每个字符出现的次数 charset list(freq.keys()) # 去重后的字符列表 char_to_idx {ch: i for i, ch in enumerate(charset)} C len(charset) # 2. 构建KMP next数组 (这里构建长度为L的数组next[0]-1) next_arr [-1] * (L 1) i, j 0, -1 while i L: while j 0 and T[i] ! T[j]: j next_arr[j] i 1 j 1 next_arr[i] j # 3. 构建转移矩阵 trans[state][char_idx] - next_state # 状态范围: 0 ~ L (L为非法态) trans [[0] * C for _ in range(L 1)] for state in range(L 1): for idx, ch in enumerate(charset): if state L and ch T[state]: trans[state][idx] state 1 else: if state 0: trans[state][idx] 0 else: # 关键回退到next_arr[state]并查询其转移 trans[state][idx] trans[next_arr[state]][idx] # 4. 动态规划 (滚动数组) # dp[state]: 当前长度为i时处于状态state的方案数 dp [0] * L dp[0] 1 # 长度为0状态为0 for _ in range(N): new_dp [0] * L for state in range(L): if dp[state] 0: continue # 遍历字符集已去重利用频率一次性累加 for idx, ch in enumerate(charset): next_state trans[state][idx] if next_state L: # 确保不进入非法态 # 累加 freq[ch] * dp[state] 种方案 new_dp[next_state] (new_dp[next_state] freq[ch] * dp[state]) % MOD dp new_dp # 5. 答案是所有合法状态的和 ans sum(dp) % MOD return ans测试用例与验证 为了确保代码正确必须用多种情况测试。基础测试N1, S“a“, T“a“。只能构造一位密码“a“但包含了T答案应为0。小型测试N2, S“ab“, T“aa“。可能密码aa, ab, ba, bb。其中aa包含T所以合法密码有3种。程序应返回3。包含重复字符的SN2, S“aa“, T“a“。每位有两个‘a‘可选。总共有2*24种可能序列aa1, aa2, aa3, aa4这里用下标区分不同位置的‘a‘。但所有序列都包含子串“a“所以答案为0。如果按去重字符集算‘a‘只算一次会得到错误答案。我们的代码使用freq[‘a‘]2能正确处理。长串测试N10, S“abc“, T“abc“。计算不包含“abc“的密码数。可以手动计算或与暴力枚举小范围对比验证。边界测试T为空串怎么办通常题目保证T非空但代码中最好处理。N0怎么办构造空密码如果T非空空密码不包含T答案应为1。但题目通常N1。实操心得在实现时最容易出错的地方有两个。一是字符集遍历务必弄清题目中S的含义是“每位可选的字符列表”还是“字符集合”。如果是列表即允许重复选择同一字符的不同“位置”就必须遍历S的每个字符或使用频率统计。二是KMP状态转移矩阵trans的构建特别是当state L非法态时的处理。在我们的定义中trans[L][c]其实不会被用到因为动态规划不会从非法态转移。但为了逻辑完整trans矩阵通常还是计算到L。8. 举一反三问题变体与扩展思考“设计密码”这个问题是一个非常好的框架稍加改动就能衍生出许多有趣的变体这些变体在面试和竞赛中也时常出现。变体1求至少包含一个禁忌串的方案数原题是“不能包含”。如果问题是“至少包含一次”那么答案就是总方案数M^N减去“完全不包含”的方案数即我们刚才算的。这就是补集思想的典型应用。变体2多个禁忌串如果不止一个不良字符串T而是有一个禁忌串的集合{T1, T2, ..., Tk}密码不能包含其中任何一个。这就是多模式匹配问题。此时KMP状态机需要升级为Aho-CorasickAC自动机。AC自动机可以看作是KMP在树形结构Trie树上的扩展它能同时匹配多个模式串。动态规划的状态就变成了在AC自动机上的节点状态转移就是沿着自动机的边对应字符走并且要避免走到任何代表某个模式串终结的节点或其fail链上的终结节点如果允许重叠匹配。状态数等于AC自动机的节点数动态规划的复杂度是O(N * 节点数 * 字符集大小)。变体3求恰好包含k次禁忌串的方案数这是一个更复杂的计数问题需要结合动态规划和自动机并增加一维状态来记录已经匹配的次数。定义dp[i][j][c]为构造了前i位处于自动机状态j且已经完整匹配了禁忌串c次的方案数。转移时如果一次转移导致完成了新的匹配即进入或经过终止状态则c加1。最终答案是dp[N][*][k]的和。这属于“带约束的字符串计数”问题。变体4期望长度或概率如果问题不是计数而是问随机生成密码每位从S中等概率随机选取直到第一次出现禁忌串T时期望的长度是多少这就变成了一个概率DP或马尔可夫链的吸收时间问题。我们可以建立类似的状态机其中状态L是吸收态一旦进入就停止。然后求解从状态0开始到达吸收态的期望步数。这需要解一个线性方程组。扩展思考为什么是KMP而不是其他算法为什么我们选择KMP来构建状态机而不是更简单的暴力匹配因为KMP的next数组提供了在匹配失败时最长的已匹配前缀信息这正好对应了“当前已构造字符串的后缀与T的匹配程度”。这个“匹配程度”就是我们需要在动态规划中记录的状态。如果使用暴力匹配状态就需要记录整个当前字符串的后L-1位状态数会爆炸M^(L-1)完全不可行。KMP将状态压缩到了O(L)级别这是问题得以解决的关键。通过这道“设计密码”题我们深入掌握了字符串匹配、有限状态自动机与动态规划这三者结合的经典范式。下次当你遇到需要在字符串构造过程中避免某些模式或者统计满足特定模式条件的字符串数量时不妨想想这个KMPDP的框架它很可能就是打开问题之门的钥匙。在实际开发中这种思想对于构建高效的内容过滤器或序列生成器也有着重要的借鉴意义。