实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-strstr
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
-
暴力思路:
称haystack为主串,needle为子串
利用指针 i , j 和辅助指针 k ,指针 i 用于记录主串开始查找的角标, 指针 j 用于 记录 查找匹配的角标 , 辅助指针 k 用于 每个字符匹配成功,依次往后移动.一:外循环的循环条件为 haystack.length() - needle.length() + 1,因为防止角标溢出,
循环条件为什么要加1 ,比如 needle参数 是 aa ,那么他的长度为2,但角标只有0和1,那么减去2之后,就减多了1,就加回1,可以通过一个简单的事例推一下这个循环条件二:中间逻辑条件: 如果字符不相等,直接break内循环,开始下一个外循环,如果字符相等,那么辅助指针就k++,开始下一个字串的配对三:如何判断匹配完成? : 在内循环中,如果没有被break,则证明已经完全遍历了一遍needle ,那么 判断 j 是否到达了needle的末尾,如果到了末尾则返回成功匹配字符串开始的角标 i
public static int strStr(String haystack, String needle) {
if (needle.equals(""))
return 0;
// 循环条件为什么要加1 ,比如 needle参数 是 aa ,那么他的长度为2,但角标只有0和1,那么减去2之后,就减多了1,就加回1,可以通过一个简单的事例推一下这个循环条件
for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
int k = i;
int j = 0;
for (; j < needle.length(); j++) {
if (haystack.charAt(k) != needle.charAt(j)) {
break;
}
k++;
}
// 在上面的for循环中,如果没有被break,则证明已经完全遍历了一遍needle ,那么 判断 j 是否到达了needle的末尾,如果到了末尾则返回成功匹配字符串开始的角标 i
if (j == needle.length())
return i;
}
return -1;
}
- kmp思路:
称haystack为主串,needle为子串
用两个指针 i 和 j 来记录 主串和子串的角标
一:从左往右一个一个字符匹配
二:如果字符相等,则开始下一个字符匹配 i++ j++
三:否则指针 i 回退到 刚开始匹配的角标的后一位, 即 i - j + 1 ,子串角标归零 j = 0;
四:while循环结束后,则证明主串或者子串有一方已经到达了末尾,那么就判断子串角 标 j 是否等于子串的末尾,即j == 子串.length,如果到达了末尾,即完成了匹配,返回刚开始匹配的第一个角标的位置,即 i - j
//created by Fivezm on 2019.7.19 kmp解法
public static int strStr(String haystack, String needle) {
char[] haystackArr = haystack.toCharArray();
char[] needleArr = needle.toCharArray();
// 两个指针,一个记录主串,一个记录子串
int i = 0;
int j = 0;
//当指针都不超出彼此的字符串长度时循环
while (i < haystackArr.length && j < needleArr.length) {
//如果 这两个字符相等,那么匹对下一个字符是否相等
if (haystackArr[i] == needleArr[j]) {
i++;
j++;
} else { // 如果字符不相等,i 回退到 原本的位置后一位的下标 , j 归零
i = i - j + 1;
j = 0;
}
}
// 如果 j 角标到达了 子串末尾,则证明匹配匹配成功,返回 主串中 i 开始角标的位置
if (j == needleArr.length)
return i - j;
return -1;
}
网友评论