[LeetCode]28.实现strStr()(Java)
2021/11/23 17:11:57
本文主要是介绍[LeetCode]28.实现strStr()(Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题地址: implement-strstr
题目描述:
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回 -1 。
说明:
当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1:
输入:haystack = "hello", needle = "ll"
输出:2
示例 2:
输入:haystack = "aaaaa", needle = "bba"
输出:-1
示例 3:
输入:haystack = "", needle = ""
输出:0
提示:
0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 仅由小写英文字符组成
解答方法:
1.
class Solution { public int strStr(String haystack, String needle) { if(haystack.equals("")&&needle.equals(""))return 0; if(haystack.equals("")&&!needle.equals(""))return -1; int sum = 0; boolean flag = false; int length = haystack.length() - needle.length() + 1; while(sum <= length){ if(haystack.startsWith(needle)){ flag = true; break; }else{ sum++; if(haystack.length()>1) haystack = haystack.substring(1); } } if(flag == false)sum = -1; return sum; }}
感觉这样不走心的刷题好没意义呀!下次一定对着优秀的解法好好复习复习,哭!
2.评论中解法
class Solution { // KMP 算法 // ss: 原串(string) pp: 匹配串(pattern) public int strStr(String ss, String pp) { if (pp.isEmpty()) return 0; // 分别读取原串和匹配串的长度 int n = ss.length(), m = pp.length(); // 原串和匹配串前面都加空格,使其下标从 1 开始 ss = " " + ss; pp = " " + pp; char[] s = ss.toCharArray(); char[] p = pp.toCharArray(); // 构建 next 数组,数组长度为匹配串的长度(next 数组是和匹配串相关的) int[] next = new int[m + 1]; // 构造过程 i = 2,j = 0 开始,i 小于等于匹配串长度 【构造 i 从 2 开始】 for (int i = 2, j = 0; i <= m; i++) { // 匹配不成功的话,j = next(j) while (j > 0 && p[i] != p[j + 1]) j = next[j]; // 匹配成功的话,先让 j++ if (p[i] == p[j + 1]) j++; // 更新 next[i],结束本次循环,i++ next[i] = j; } // 匹配过程,i = 1,j = 0 开始,i 小于等于原串长度 【匹配 i 从 1 开始】 for (int i = 1, j = 0; i <= n; i++) { // 匹配不成功 j = next(j) while (j > 0 && s[i] != p[j + 1]) j = next[j]; // 匹配成功的话,先让 j++,结束本次循环后 i++ if (s[i] == p[j + 1]) j++; // 整一段匹配成功,直接返回下标 if (j == m) return i - m; } return -1; } }
这篇关于[LeetCode]28.实现strStr()(Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)