28.Implement strStr()

【题目】

Implement strStr().

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

實現strStr（）函數。

給定一個haystack字符串和一個針字符串，在haystack字符串中找出針字符串出現的第一個位置（從0開始）。

如果不存在，則返回-1。

Example 1:

Input:
 haystack = "hello", needle = "ll"

Output:
 2

Example 2:

Input:
 haystack = "aaaaa", needle = "bba"

Output:
 -1

【思路】

這題就是要實做 JAVA 的 indexof 的概念，但這邊要小心陷阱，就是如果例題是 "mississippi" ， 目標值是 "issip"

在中間檢核時如果寫法不對就會中上述題的陷阱，所以指標的控制要注意。

【解法】

☆JAVA

注意題目: For the purpose of this problem, we will return 0 whenneedleis an empty string.

public static int strStr(String haystack, String needle) {
    if(haystack==null || needle==null || needle.length() == 0)    //如果為null則回傳0 or 目標值長度為0也傳回0
        return 0;

    for(int i=0; i<haystack.length(); i++){                       
        if(i + needle.length() > haystack.length())               //如果剩餘檢核值haystack長度 < needle 代表錯誤 回傳 -1
            return -1;
        if(needle.charAt(0)==haystack.charAt(i)){                 //先用第一個值去比 如果比到做後續
            int m = i;                                            //先存起來 後續用
            for(int j=0; j<needle.length(); j++){                 
                if(needle.charAt(j)==haystack.charAt(m)){         //一個一個比對 如果正確 比下一個(m) 錯誤就 beeak
                    m++;
                }else{
                    break;
                }
            }
            if(needle.length() == (m-i)){                          //如果全對表示 m-i 會等同於needle的長度
                return i;
            }
        }    
    }   
    return -1;
}

然後我有看到有人用subString去比較XD 如果後續面試考官說可以的話 用這個比較快XD

public int strStr(String haystack, String needle) {
    int l1=haystack.length();
    int l2=needle.length();
    if(l1<l2)
    {
        return -1;
    }
    else if(l2==0)
    {
        return 0;
    }
    for(int i=0;i<=l1-l2;i++)
    {
        if(haystack.substring(i,i+l2).equals(needle))
        {
            return i;
        }
    }
    return -1;
}

☆Python

Python 我這邊偷懶直接用 陣列 來比較 ,所以會像卷積一樣平行滑動過去掃描 , 對了就回傳嚕

def strStr(self, haystack, needle):
    if(haystack is None or needle is None or len(needle) == 0):
        return 0;
    for i in range(len(haystack)):
        if haystack[i:i+len(needle)] == needle:
            return i;
    return -1;