LeetCode-Implement strStr()的一種算法

題目連結：https://leetcode.com/problems/implement-strstr/description/

Implement strStr().

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

Example 1:

Input: haystack = “hello”, needle = “ll”

Output: 2

Example 2:

Input: haystack = “aaaaa”, needle = “bba”

Output: -1

題目要求我們找出haystack字元串中needle字元段的所在位置，存在傳回該位置，否則傳回-1。

算法很簡單，先判斷needle字元段是否為“”，是則直接傳回0即可。随後判斷haystack是否為“”且needle是否不為“”，是則傳回-1。

而後循環周遊haystack的每一個字元，找到對應needle的第一個字元的字元位置，判斷其是否等于needle，是則傳回位置，否則繼續循環周遊到最後。

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle == "") return 0;	//判斷
        else if (haystack == "" && needle != "") return -1;	//判斷
        for (int i = 0; i < haystack.length(); i++) {	//循環周遊
            if (haystack[i] == needle[0]) {		//判斷第一個字元是否相等
                int j = needle.length();
                //判斷該位置開始的字元串是否存在與needle相同的部分
                if (i+j <= haystack.length() && haystack.substr(i, j) == needle) {
                    return i;
                }
            }
        }
        return -1;
    }
};
           

整個算法難度不大，麻煩的地方在于判斷haystack或needle為“”的情況。