2023-07-10|閱讀時間 ‧ 約 7 分鐘

【LittleDuck_LeetcodeNote】28 - Find the Index of the First...

【Instagram】 / 【巴哈姆特小屋】 / 【Vocus方格子】 / 【Medium】
喜歡的話就按個愛心或贊助ㄅ。

A realistic, brightly colored interior home-style drawing in blue tones of a software engineer. - Leonardo.ai

Question and Hints

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.

First Solution

💡 如果needle比haystack長，就不用看了，一定找不到。

這邊的思路是以 i 作為索引，一個一個去和needle的第一個字元做比對，
相同就用 j 作為索引，確認後續的字元有沒有一樣，
如果都有，就回傳 i 的位置，
如果有一個字不同，就回到 i 的位置繼續往下找。

class Solution {
    public int strStr(String haystack, String needle) {
        int i=0;

        if(needle.length() > haystack.length())
            return -1;

        while(i < haystack.length()){
            if(haystack.charAt(i) == needle.charAt(0)){
                int j=0;
                for(; j < needle.length(); j++){
                    if(i+j >= haystack.length())
                        return -1;
                    if(haystack.charAt(i+j) != needle.charAt(j))
                        break;
                }
                if(j == needle.length())
                    return i;
            }
            i++;
        }
        return -1;
    }
}

⏰ Runtime: 1 ms (39.21 %)

📦 Memory: 40.2 MB (94.80 %)

Upgrade Solution

💡 思路是相同的，不過這個作法只用了一個for loop，所以可以更快。

一樣用 i 去做搜尋的索引，
差別在遇到和needle相同的字元後，
原本First Solution的做法是先用 j (nLen) 檢查後面的字元是否都一樣，
而這邊的作法是讓 i 和 nLen同時前進，
如果不一樣，i 就退一格繼續搜尋。
原本是想說 i 要固定，
這樣找到和needle相同的部分時才可以找到開頭的索引，
但如果 i 真的找到needle的最後一個字元，
那這時讓 i 往後退 nLen格，
其實就可以找到開頭的索引了。
如果照原本的做法，i 是會重複走到 j 的搜尋過程的，
因此這個做法可以少走一些冤枉路，比較簡潔，
而且不用設定例外情況，
是個相當聰明的寫法。

class Solution {
    public int strStr(String haystack, String needle) {
        int hLen = haystack.length();
        int nLen = needle.length();
        int nIndex = 0;
        for(int i=0; i<hLen; i++){
            // as long as the characters are equal, increment needleIndex
            if(haystack.charAt(i)==needle.charAt(nIndex)){
                nIndex++;
            }
            else{
                // start from the next index of previous start index
                i=i-nIndex;
                // needle should start from index 0
                nIndex=0;
            }
            // check if needleIndex reached needle length
            if(nIndex==nLen){
                // return the first index
                return i-nLen+1;
            }
        }
        return -1;
    }
}