28.Find the Index of the First Occurrence in a String

Description

	#28	Find the Index of the First Occurrence in a String	Easy
		String	Top 150
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.

State Machine

Runtime 1ms		Memory 41.15MB

class Solution {
    enum State {
        NOT_MATCHED,
        MATCHING,
    }
    public int strStr(String haystack, String needle) {
        State s = State.NOT_MATCHED;
        int start = -1;
        for(int i = 0; i < haystack.length(); i++) {
            switch(s) {
                case State.NOT_MATCHED: {
                    if(haystack.charAt(i) == needle.charAt(0)) {
                        if(needle.length() == 1) return i;
                        s = State.MATCHING;
                        start = i;
                        break;
                    } else {
                        break;
                    }
                }
                case State.MATCHING: {
                    if(haystack.charAt(i) != needle.charAt(i - start)) {
                        s = State.NOT_MATCHED;
                        i = start;
                        start = -1; 
                        break;
                    } else {
                        if(i - start + 1== needle.length()) return start;
                        break;
                    }
                }
                default: break;
            }
        }
        return -1;
    }
}

Substring

Runtime 0ms		Memory 41.15MB

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

        // or, return haystack.indexOf(needle);
    }
}