LeetCode-字元串-28 實作 strStr() 函數

題幹

實作 strStr() 函數。

給定一個 haystack 字元串和一個 needle 字元串，在 haystack 字元串中找出 needle 字元串出現的第一個位置 (從0開始)。如果不存在，則傳回  -1。

示例 1:

輸入: haystack = "hello", needle = "ll"

輸出: 2

示例 2:

輸入: haystack = "aaaaa", needle = "bba"

輸出: -1

說明:

當 needle 是空字元串時，我們應當傳回什麼值呢？這是一個在面試中很好的問題。

對于本題而言，當 needle 是空字元串時我們應當傳回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。

解析

解答1

class Solution 
{
public:
    int strStr(string haystack, string needle) 
	{
        if (needle.size()==0)
            return 0;
        if (needle.size() > haystack.size())
            return -1;
        int j=0;//needle指針
        int i=0;
        for (i = 0; i < haystack.size(); ++i) 
		{
            if (j==needle.size()){//判斷完成
                return i - needle.size();
            }
            if (haystack[i] == needle[j])
			{
                j++;
            } 
			else
			{
                i -= j;
                j=0;
            }
        }
        if (j==needle.size())
		{//判斷完成
            return i - needle.size();
        }
        return -1;
    }
};
           

解答2

class Solution 
{
public:
    int strStr(string haystack, string needle) 
	{
        if(needle == "")
            return 0;
        int pos = haystack.find(needle);
        return pos;
    }
};