iis 7.0 网站配置,公司注册名字审核网,网站关于我们示例,网站开发步骤需求分析实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串#xff0c;在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在#xff0c;则返回 -1。
示例 1:
输入: haystack hello, needle ll
输出: 2示例…实现 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() 定义相符。
class Solution {
public:int strStr(string haystack, string needle) {if (haystack.size() needle.size()) {return -1;}int i, j;for (i0; ihaystack.size() - needle.size()1; i) {for (j0; jneedle.size(); j) {if (haystack[ij] ! needle[j]) {break;}}if (j needle.size()) {return i;}}return -1;}
};Sunday 算法
class Solution {
public:int strStr(string haystack, string needle) {int hsize haystack.size();int nsize needle.size();unordered_mapchar, int offset;for(int i0; insize; i) {offset[needle[i]] nsize - i;}int i0;while(ihsize-nsize) {if (haystack.substr(i, nsize) needle) {return i;} else {if (insize hsize-1) {return -1;} else {if (offset.find(haystack[insize]) ! offset.end()) {i offset[haystack[insize]];} else {i nsize1;}}}}return -1;}
};KMP 算法
class Solution {
public:int strStr(string haystack, string needle) {if (needle.empty()) {return 0;}int hSize haystack.size();int nSize needle.size();vectorint next(nSize, 0);get_next(next, needle);int i0;int j0;while(ihSize) {if (haystack[i] needle[j]) {i;j;} else {if (j 0) {i;} else {jnext[j-1];}}if (jnSize) {return i-j;}}return -1;}void get_next(vectorint next, const string needle) {int n needle.size();int i1, j0;while(in) {if (needle[i] needle[j]) {j;next[i]j;i;} else {if (j 0) {next[i]0;i;} else {j next[j-1];}}}}
};参考链接
bilibili KMP讲解 来源力扣LeetCode
