南昌门户网站,wordpress菜单项目边距和填充,各大行业网站,网站城市跳转怎么做文章目录 一、题目二、C# 题解 一、题目 给你两个字符串 haystack 和 needle #xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标#xff08;下标从 0 开始#xff09;。如果 needle 不是 haystack 的一部分#xff0c;则返回 -1 。 点击此处跳转… 文章目录 一、题目二、C# 题解 一、题目 给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标下标从 0 开始。如果 needle 不是 haystack 的一部分则返回 -1 。 点击此处跳转题目。
示例 1 输入 haystack “sadbutsad”, needle “sad” 输出 0 解释 “sad” 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 所以返回 0 。 示例 2 输入 haystack “leetcode”, needle “leeto” 输出 -1 解释 “leeto” 没有在 “leetcode” 中出现所以返回 -1 。 提示
1 haystack.length, needle.length 104haystack 和 needle 仅由小写英文字符组成
二、C# 题解 题目直接调用库函数即可。这里复习一下 KMP 算法首先构造 next 数组。注意next 数组长度为 needle 1。采取这样的做法是为了使后缀指针 j 不会指向 -1这里 next[0] 的位置就充当了 next[-1] 的位置以免数组越界报错。 为什么 j 一定要指向 -1 呢不可以指向 0 就停止回退吗不行因为 j 指向 0 时无法区分 j 此时是回退到 0此时 j 不应该 1因为下一次还要指向第一个字符即 j 0还是指前后缀的最后一位相等此时 j 应该 1下一次 j 1。 正因 next 数组长度为 needle 1else j next[j 1] - 1; 该段代码需要对 j 先 1取出 next 值后再 -1。完整代码如下
public class Solution {public int StrStr(string haystack, string needle) {int[] next GetNext(needle); // 获取 next 数组int i 0, j 0; // i 指向 haystackj 指向 needlewhile (i haystack.Length) {// j 回退到 -1 或字符相同则进行下一位匹配if (j -1 || haystack[i] needle[j]) { i; j; }else j next[j 1] - 1; // 否则j 依据 next 数组回退if (j needle.Length) return i - j; // j 遍历完 needle返回 needle 起始位置}return -1;}// 获取 next 数组public int[] GetNext(string needle) {int[] next new int[needle.Length 1]; // next 长度为 needle 1next[0] 空着作用是避免 j 越界next[1] 0; // next[1,n] 存储 needle 对应的字符下标int i 1, j 0; // i 指向 needle[0,i] 后缀末尾j 指向 needle[0,i] 前缀末尾while (i needle.Length) {// j 回退到 0 或后缀相同则 i、j 一同前进并给 next 赋值if (j 0 || needle[i - 1] needle[j - 1]) next[i] j;else j next[j]; // 否则j 回退}return next;}
}时间复杂度 O ( m n ) O(mn) O(mn)其中 m m m 为 haystack 长度n 为 needle 长度。空间复杂度 O ( n ) O(n) O(n)。 《大话数据结构》中提到了 KMP 的优化改动为 GetNext 函数中的如下代码即加了一行判断处理。下面对改代码做出简略解释 // j 回退到 0 或后缀相同则 i、j 一同前进并给 next 赋值if (j 0 || needle[i - 1] needle[j - 1]) if (needle[i] needle[j]) next[i] next[j];else next[i] j;else j next[j]; // 否则j 回退即判断前后缀后一个字符是否相同。如果相同直接将之前的 next 结果复制过来否则按照之前的处理即可。下面举例说明这样做的正确性图中黑色箭头表示 i红色箭头表示 j。 可以看到最后一位不相同按照原本的规则next[6] 应取 3绿色箭头指向位置从 1 开始计数。但是由于前缀和后缀都是 ab且其后一位均为 e。因此将 next[6] 赋值为 next[3]即 next[6] next[3] 1。 为什么可以这样呢因为 next[6] 是 e已经不匹配了那么跳到相同字符的 next[3] 处也一定不匹配因此直接跳到 next[next[3]]蓝色箭头指向位置就好啦完整代码如下
public class Solution {public int StrStr(string haystack, string needle) {int[] next GetNext(needle); // 获取 next 数组int i 0, j 0; // i 指向 haystackj 指向 needlewhile (i haystack.Length) {// j 回退到 -1 或字符相同则进行下一位匹配if (j -1 || haystack[i] needle[j]) { i; j; }else j next[j 1] - 1; // 否则j 依据 next 数组回退if (j needle.Length) return i - j; // j 遍历完 needle返回 needle 起始位置}return -1;}// 获取 next 数组public int[] GetNext(string needle) {int[] next new int[needle.Length 1]; // next 长度为 needle 1next[0] 空着作用是避免 j 越界next[1] 0; // next[1,n] 存储 needle 对应的字符下标int i 1, j 0; // i 指向 needle[0,i] 后缀末尾j 指向 needle[0,i] 前缀末尾while (i needle.Length) {// j 回退到 0 或后缀相同则 i、j 一同前进并给 next 赋值if (j 0 || needle[i - 1] needle[j - 1]) {if (needle[i] needle[j]) next[i] next[j];else next[i] j;}else j next[j]; // 否则j 回退}return next;}
}时间复杂度 O ( m n ) O(mn) O(mn)。空间复杂度 O ( n ) O(n) O(n)。
