3303. 第一个几乎相等子字符串的下标
给你两个字符串 s
和 pattern
。
如果一个字符串 x
修改 至多 一个字符会变成 y
,那么我们称它与 y
几乎相等 。
请你返回 s
中下标 最小 的 子字符串 ,它与 pattern
几乎相等 。如果不存在,返回 -1
。
子字符串 是字符串中的一个 非空、连续的字符序列。
示例 1:
输入:s = "abcdefg", pattern = "bcdffg"
输出:1
解释:
将子字符串 s[1..6] == "bcdefg"
中 s[4]
变为 "f"
,得到 "bcdffg"
。
示例 2:
输入:s = "ababbababa", pattern = "bacaba"
输出:4
解释:
将子字符串 s[4..9] == "bababa"
中 s[6]
变为 "c"
,得到 "bacaba"
。
示例 3:
输入:s = "abcd", pattern = "dba"
输出:-1
示例 4:
输入:s = "dde", pattern = "d"
输出:0
提示:
1 <= pattern.length < s.length <= 3 * 105
s
和 pattern
都只包含小写英文字母。进阶:如果题目变为 至多
k
个 连续 字符可以被修改,你可以想出解法吗?
原站题解
python3 解法, 执行用时: 1819 ms, 内存消耗: 29.2 MB, 提交时间: 2024-10-19 14:14:05
class Solution: def calc_z(self, s: str) -> list[int]: n = len(s) z = [0] * n box_l = box_r = 0 # z-box 左右边界 for i in range(1, n): if i <= box_r: z[i] = min(z[i - box_l], box_r - i + 1) # 改成手动 if 可以加快速度 while i + z[i] < n and s[z[i]] == s[i + z[i]]: box_l, box_r = i, i + z[i] z[i] += 1 return z def minStartingIndex(self, s: str, pattern: str) -> int: pre_z = self.calc_z(pattern + s) suf_z = self.calc_z(pattern[::-1] + s[::-1]) suf_z.reverse() # 也可以不反转,下面写 suf_z[-i] m = len(pattern) for i in range(m, len(s) + 1): if pre_z[i] + suf_z[i - 1] >= m - 1: return i - m return -1
java 解法, 执行用时: 54 ms, 内存消耗: 46.6 MB, 提交时间: 2024-10-19 14:13:51
class Solution { public int minStartingIndex(String s, String pattern) { int[] preZ = calcZ(pattern + s); int[] sufZ = calcZ(rev(pattern) + rev(s)); // 可以不反转 sufZ,下面写 sufZ[sufZ.length - i] int n = s.length(); int m = pattern.length(); for (int i = m; i <= n; i++) { if (preZ[i] + sufZ[sufZ.length - i] >= m - 1) { return i - m; } } return -1; } private int[] calcZ(String S) { char[] s = S.toCharArray(); int n = s.length; int[] z = new int[n]; int boxL = 0; int boxR = 0; // z-box 左右边界 for (int i = 1; i < n; i++) { if (i <= boxR) { z[i] = Math.min(z[i - boxL], boxR - i + 1); } while (i + z[i] < n && s[z[i]] == s[i + z[i]]) { boxL = i; boxR = i + z[i]; z[i]++; } } return z; } private String rev(String s) { return new StringBuilder(s).reverse().toString(); } }
cpp 解法, 执行用时: 95 ms, 内存消耗: 71.7 MB, 提交时间: 2024-10-19 14:13:37
class Solution { vector<int> calc_z(string s) { int n = s.length(); vector<int> z(n); int box_l = 0, box_r = 0; // z-box 左右边界 for (int i = 1; i < n; i++) { if (i <= box_r) { z[i] = min(z[i - box_l], box_r - i + 1); } while (i + z[i] < n && s[z[i]] == s[i + z[i]]) { box_l = i; box_r = i + z[i]; z[i]++; } } return z; } public: int minStartingIndex(string s, string pattern) { vector<int> pre_z = calc_z(pattern + s); ranges::reverse(pattern); ranges::reverse(s); vector<int> suf_z = calc_z(pattern + s); ranges::reverse(suf_z); // 也可以不反转,下面写 suf_z[suf_z.size() - i] int m = pattern.length(); for (int i = m; i <= s.length(); i++) { if (pre_z[i] + suf_z[i - 1] >= m - 1) { return i - m; } } return -1; } };
golang 解法, 执行用时: 38 ms, 内存消耗: 10.5 MB, 提交时间: 2024-10-19 14:13:24
func calcZ(s string) []int { n := len(s) z := make([]int, n) boxL, boxR := 0, 0 // z-box 左右边界 for i := 1; i < n; i++ { if i <= boxR { z[i] = min(z[i-boxL], boxR-i+1) } for i+z[i] < n && s[z[i]] == s[i+z[i]] { boxL, boxR = i, i+z[i] z[i]++ } } return z } func rev(s string) string { t := []byte(s) slices.Reverse(t) return string(t) } func minStartingIndex(s, pattern string) int { preZ := calcZ(pattern + s) sufZ := calcZ(rev(pattern) + rev(s)) slices.Reverse(sufZ) // 也可以不反转,下面写 sufZ[len(sufZ)-i] m := len(pattern) for i := m; i <= len(s); i++ { if preZ[i]+sufZ[i-1] >= m-1 { return i - m } } return -1 }