如何制作一个简单的网站,如何设计网站导航,苏州 互联网,网站开发验收模板1.题目 给你两个字符串 haystack 和 needle #xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标#xff08;下标从 0 开始#xff09;。如果 needle 不是 haystack 的一部分#xff0c;则返回 -1 。
2.示例 3.思路
回溯算法#xff1a;首先将…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 i0;i hays.length;i){if (hays[i] needs[j]){count;if (jneeds.length-1){dex i-(needs.length-1);break;}j;continue;}else { ii-count;j 0; count0;}}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 {
// 如果出现不匹配则进行回溯ii-count;j 0;count 0;}}
// 判断是否有足够的countif (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)。
会了试试挑战下一题♪∀● ●´∀♪
LeetCode150道面试经典题--验证回文串(简单)_Alphamilk的博客-CSDN博客
