1.题目
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1。
2.示例
编辑
3.思路
回溯算法：首先将字符串拆分成字符数组，然后对数组进行遍历，进行一一匹配，如果出现匹配失败则回溯到一开始的数组重新进行下一次匹配。
LeetCode代码：
class Solution { public int strStr(String haystack, String needle) { char hays[]=haystack.toCharArray(); char needs[] = needle.toCharArray(); int dex = 0; int count = 0; int j = 0; for (int i=0;i< hays.length;i++){ if (hays[i] == needs[j]){ count++; if (j==needs.length-1){ dex = i-(needs.length-1); break; } j++; continue; }else { i=i-count;j = 0; count=0;} } if (count!=needs.length){ dex = -1; } return dex; } }
案例详细代码:
package LeetCode09; public class javaDemo { public static void main(String[] args) { // 查找字符串第一个出现 String haystack = "mississippi"; String needle = "issi"; char hays[] = haystack.toCharArray(); char needs[] = needle.toCharArray(); // 设置计数器，初始化下脚标 int dex = 0; int count = 0; int j = 0; // 遍历数组 for (int i = 0; i < hays.length; i++) { // 判断如果当前字符匹配则往下走 if (hays[i] == needs[j]) { count++; if (j == needs.length - 1) { dex = i - (needs.length - 1); break; } j++; continue; } else { // 如果出现不匹配则进行回溯 i=i-count; j = 0; count = 0; } } // 判断是否有足够的count if (count != needs.length) { dex = -1; } System.out.println(dex); } }
总结：
时间复杂度：n 为原串的长度，m 为匹配串的长度。其中枚举的复杂度为 O(n−m)O(n - m)O(n−m)，构造和比较字符串的复杂度为 O(m)O(m)O(m)。整体复杂度为 O((n−m)∗m)O((n - m) * m)O((n−m)∗m)。
空间复杂度：O(1)O(1)O(1)。
