題目:
Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: Example 2: Clarification: What should we return when is an empty string? This is a great question to ask during an interview. For the purpose of this problem, we will return 0 when is an empty string. This is consistent to C's strstr() and Java's indexOf(). | 實作 strStr() 函數。 給定一個 haystack 字元串和一個 needle 字元串,在 haystack 字元串中找出 needle 字元串出現的第一個位置 (從0開始)。如果不存在,則傳回 -1。 示例 1: 示例 2: 說明: 當 是空字元串時,我們應當傳回什麼值呢?這是一個在面試中很好的問題。 對于本題而言,當 是空字元串時我們應當傳回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。 |
思路:haystack從前往後查找。
class Solution {
public:
int strStr(string haystack, string needle) {
int m=haystack.size(),n=needle.size(),i,j,p=0;
if(n==0) return 0;
if(m<n) return -1;
for(i=0;i<=m-n;++i)
{
p=0;
for(j=0;j<n;++j)
{
if(haystack[i+j]==needle[j])
p++;
}
if(p==n) return i;
}
return -1;
}
};