面试经典150题——Day23

一、题目

28. Find the Index of the First Occurrence in a String

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = “sadbutsad”, needle = “sad”
Output: 0
Explanation: “sad” occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2:

Input: haystack = “leetcode”, needle = “leeto”
Output: -1
Explanation: “leeto” did not occur in “leetcode”, so we return -1.

Constraints:

1 <= haystack.length, needle.length <= 104
haystack and needle consist of only lowercase English characters.

题目来源： leetcode

二、题解

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n1 = haystack.length();
        int n2 = needle.length();
        int i = 0;
        int res = n1;
        while(i < n1){
            int index = i;
            int j = 0;
            bool flag = true;
            for(;j < n2;j++){
                if(haystack[i++] != needle[j]){
                    flag = false;
                    break;
                }
            }
            i = index + 1;
            if(flag) res = min(index,res);
        }
        if(res == n1) return -1;
        else return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24