首页 > 代码库 > Leetcode | Implement strStr()

Leetcode | Implement strStr()

2024-07-04 12:15:20   224人阅读

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

此题我觉得并不是真要你写出kmp算法。 指针暴力法我觉得可能是考察点。而且要accept的话，必须要忽略后面一段不可能匹配的串。指针的操作要非常小心。

Of course, you can demonstrate to your interviewer that this problem can be solved using known efficient algorithms such as Rabin-Karp algorithm, KMP algorithm, and the Boyer-Moore algorithm. Since these algorithms are usually studied in advanced algorithms class, for an interview it is sufficient to solve it using the most direct method — The brute force method.

非指针代码很好小，很难有错。最长扫描n1-n2+1个就够了。

 1 class Solution {
 2 public:
 3     char *strStr(char *haystack, char *needle) {
 4         if (haystack == NULL || needle == NULL) return NULL;
 5         int n1 = strlen(haystack);
 6         int n2 = strlen(needle);
 7         int j; 
 8         
 9         for (int i = 0; i < n1 - n2 + 1; ++i) {
10             j = 0;
11             while (j < n2 && needle[j] == haystack[i + j]) j++;
12             if (j == n2) return haystack + i;
13         }
14         return NULL;
15     }
16 };

c指针代码：

 1 class Solution {
 2 public:
 3     char *strStr(char *haystack, char *needle) {
 4         if (haystack == NULL || needle == NULL) return NULL;
 5         if (*needle == ‘\0‘) return haystack;
 6         char *ph = haystack, *pn = needle, *count = ph, *tmp;
 7         while (*pn) {
 8             if (!*count) return NULL;
 9             pn++; 
10             count++;
11         }
12         if (*needle) count--;
13         while (*count) {
14             pn = needle;
15             tmp = ph;
16             while (*pn && *tmp && *pn == *tmp) {
17                 pn++; tmp++;
18             }
19             if (!*pn) return ph;
20             ph++;
21             count++;
22         }    
23         
24         return NULL;
25     }
26 };

如果是needle是空串，返回应该是haystack整个串。

最长扫描n1-n2+1个就够了。所以要让count循环m-1次。优化后的代码如下：

 1 class Solution {
 2 public:
 3     char *strStr(char *haystack, char *needle) {
 4         if (*needle == ‘\0‘) return haystack;
 5         char *ph = haystack, *pn = needle, *count = ph, *tmp;
 6         while (*++pn) {
 7             if (!*count) return NULL;
 8             count++;
 9         }
10         while (*count) {
11             pn = needle;
12             tmp = ph;
13             while (*pn && *tmp && *pn == *tmp) {
14                 pn++; tmp++;
15             }
16             if (!*pn) return ph;
17             ph++;
18             count++;
19         }    
20         
21         return NULL;
22     }
23 };

 


联系
我们