LeetCode刷题(C++)——Implement strStr()(Easy)

xiaoxiao2021-02-28  97

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

strStr()函数用于判断字符串str2是否是str1的子串。如果是,则该函数返回str2在str1中首次出现的地址;否则,返回NULL。不存在时本题要求返回-1.

思路:暴力寻找,依次将haystack和needle的首字符进行比较,如果相同则同时比较第二个字符,直到匹配结束返回首字符在haystack中的位置。如果中间遇到不相同的字符,则needle返回第一个字符,haystack从下一个字符开始重新比较。

还有其他更高效的字符串匹配算法,比如KMP算法、Boyer-Moore算法等。

class Solution { public: int strStr(string haystack, string needle) { int len1 = haystack.size(); int len2 = needle.size(); if (len1 < len2) return -1; if ((len1 == 0 && len2 == 0) || len2 == 0) return 0; for (int i = 0; i < len1;i++) { int k = i; int j = 0; while (j < len2) { if (haystack[k] == needle[j]) { k++; j++; } else break; } if (j == len2) return i; } return -1; } };

转载请注明原文地址: https://www.6miu.com/read-76575.html

最新回复(0)