My java solution using the Sunday algorithm. 2ms.


  • 0
    Q
    public class Solution {
        public int strStr(String haystack, String needle) {
            char [] string = haystack.toCharArray();
            char [] pattern = needle.toCharArray();
            
            int stringLen = string.length;
            int patternLen = pattern.length;
            
            if(stringLen < patternLen) return -1;
            int sCount = 0, pCount = 0;
            int location = 0;
            
            while(sCount < stringLen && pCount < patternLen){
                if(string[sCount] == pattern[pCount]){
                    sCount++;
                    pCount++;
                } else {
                    sCount -= pCount;
                    int sAim = sCount + patternLen;
                    if(sAim >= stringLen) return -1;
                    char aimChar = string[sAim];
                    int pAim = patternLen - 1;
                    while(pAim >= 0){
                        if(pattern[pAim] == aimChar) break;
                        pAim--;
                    }
                    sCount = sCount + patternLen - pAim;
                    location = sCount;
                    pCount = 0;
                }
            }
    
            if(pCount < patternLen) return -1;
            return location;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.