Kimi LeetCode 3303. 第一个几乎相等子字符串的下标 Java实现

以下是 LeetCode 3303 的 Java 实现使用 Z-FunctionZ 数组 算法时间复杂度 O(n)空间复杂度 O(n)javaclass Solution {public int minStartingIndex(String s, String pattern) {int n s.length(), m pattern.length();// 正向匹配pattern s计算从 pattern 开头能匹配 s 中每个位置的最长前缀长度int[] z1 zFunction(new StringBuilder(pattern).append(s).toString());// 反向匹配reverse(pattern) reverse(s)计算从 pattern 末尾能匹配 s 中每个位置的最长后缀长度int[] z2 zFunction(new StringBuilder(pattern).reverse().append(new StringBuilder(s).reverse()).toString());// 枚举每个可能的起始位置 i// z1[pattern.length() i] 表示从 s[i] 开始正向匹配 pattern 的最长前缀长度// z2[s.length() - i] 表示从 s[i] 末尾反向匹配 pattern 的最长后缀长度// 两者之和 m - 1 说明中间最多只有 1 个字符不匹配for (int i 0; i n - m; i) {if (z1[m i] z2[n - i] m - 1) {return i;}}return -1;}// Z-Functionz[i] 表示 s[i..n) 与 s[0..n) 的最长公共前缀长度private int[] zFunction(String s) {int n s.length();int[] z new int[n];int l 0, r 0;for (int i 1; i n; i) {if (i r) {z[i] Math.min(r - i, z[i - l]);}while (i z[i] n s.charAt(z[i]) s.charAt(i z[i])) {z[i];}if (i z[i] r) {l i;r i z[i];}}return z;}}核心思路几乎相等 的定义修改至多 1 个字符后两个字符串相等即汉明距离 ≤ 1。利用 Z-Function 分别计算1. 正向匹配pattern s 的 Z 数组得到 z1[m i] — 从 s[i] 开始正向匹配 pattern 的最长前缀长度2. 反向匹配reverse(pattern) reverse(s) 的 Z 数组得到 z2[n - i] — 从 s[i] 末尾反向匹配 pattern 的最长后缀长度对于起始位置 i如果 z1[m i] z2[n - i] m - 1说明正向匹配前缀 反向匹配后缀覆盖了至少 m - 1 个字符中间最多只有 1 个字符不匹配满足几乎相等条件。复杂度维度 复杂度时间 O(n m)两次 Z-Function 均为线性空间 O(n m)两个 Z 数组示例验证输入 输出 解释sabcdefg, patternbcdffg 1 s[1..6]bcdefg改 e→f 得 bcdffgsababbababa, patternbacaba 4 s[4..9]bababa改 a→c 得 bacabasabcd, patterndba -1 无满足条件的子串sdde, patternd 0 单字符任意位置都满足0 次修改