如何检查字符串是否存在符合小写字母双射映射的模式匹配子串

核心思路 #

不需要枚举所有26!种双射映射，只需通过比对结构特征即可判断子串与模式串是否满足匹配规则，核心匹配规则可拆解为两个必满足条件：

1. 模式串中大写字母的位置，对应子串的同位置字符必须和该大写字母完全一致，大写不受映射规则影响
2. 小写字母部分需满足双向双射：模式串中相同小写字母对应子串字符必须相同，模式串中不同小写字母对应子串字符必须不同

具体实现步骤 #

• 边界预处理：若模式串长度m大于原字符串长度n，直接返回false
• 模式串预处理：
  • 记录所有大写字母的位置和对应字符，用于窗口快速剪枝
  • 生成模式串的特征序列：遍历模式串，首次出现的小写字母按顺序分配递增ID，重复出现的小写字母复用首次分配的ID，大写字母直接保留原字符
• 滑动窗口遍历原串：
  每次取长度为m的窗口，先校验大写位置是否完全匹配，不匹配直接跳过当前窗口；校验通过后，生成当前窗口的特征序列，和模式串的特征序列比对，完全一致则返回true
• 所有窗口遍历完成无匹配，返回false

示例验证：正例中模式串onecompleX的特征序列为[0,1,2,3,0,4,5,6,2,'X']，匹配子串anexampleX的特征序列完全一致，符合要求；负例中模式串AaBa的特征序列为['A',0,'B',0]，原串所有长度为4的窗口特征序列都无法匹配，返回false

时间复杂度说明 #

• 基础实现的时间复杂度为O(n*m)，其中n是原串长度，m是模式串长度，对于绝大多数常规输入场景性能足够
• 若需要优化到线性复杂度，可对特征序列计算滚动哈希，每个窗口的哈希值可在O(1)时间内算出，总时间复杂度可降至O(n+m)，怕哈希碰撞可采用双哈希策略进一步降低冲突概率

原有方案优化说明 #

原来基于Rabin-Karp枚举所有双射的方案不可行，26!的枚举量远超出计算能力，上述方案完全避开了枚举映射的步骤，通过结构特征比对直接判断匹配性，性能提升数个数量级。

内容的提问来源于stack exchange，提问作者curious.researcher