0028 - Find the Index of the First Occurrence in a String

大意

找出目標字串片段第一次出現的起始 index

例如 mississippi ，目標字串為 issip，那 index 要回傳為 4

個人思考

因為經常 Time out，我不知道是哪裡出了問題。

最初是這樣寫的，但是在測資上爆掉了：

class Solution {
    public int strStr(String haystack, String needle) {
        int sameCount = 0;
        int lastSuccess = 0;
        int count = 0;
        
        while(count < haystack.length()){
            if(sameCount == needle.length()){
                return count - sameCount;
            }

            if(haystack.charAt(count) != needle.charAt(sameCount)){
                sameCount = 0;
                if(lastSuccess != 0){
                    count = lastSuccess;
                    continue;
                }
            } else {
                sameCount++;
                lastSuccess = count;
            }
            count++;
        }

        if(sameCount == needle.length() - 1){
            return haystack.length() - sameCount;
        } else {
            return -1;
        }
    }
}

後來看了一下解答，加上理解解題思路之後，就修改成這樣：

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

        // 一定要先排除長度小於比較子字串的狀況
        if(haystack.length() < needle.length()){
            return -1;
        }
        
        // 每換一個起頭就暴力跑完子字串
        // 迴圈結束條件：如果子字串長度 <= 要比較字串長度，那就永遠都不會超過
        for(index = 0;index <= haystack.length() - needle.length(); index++){
            int subCount = 0;

            // 暴力迴圈跑完子字串，發現不同就跳迴圈
            for(subCount = 0; subCount < needle.length(); subCount++){
                if(haystack.charAt(index + subCount) != needle.charAt(subCount)){
                    break;
                }
            }

            // 只有當子字串 Count 長度等於子字串實際長度時，代表找到子字串了，回傳起始 index
            if(subCount == needle.length()){
                return index;
            }
        }

        // 如果都跑完迴圈還是找不到，那就是真的找不到
        return -1;
    }
}