Implement strStr()

Problem

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.

Solutions & Analysis

• haysand의 start, 현재 몇 개 문자가 맞았는지 count, 스트링에서의 문자 pointer i/j 선언해서 사용한다
• while 문 하나로 일치 여부 판단하면서 i++/j++, 이 때 start, count 재설정(init)를 문자가 다를 때마다 해준다

Code (Java)

code1

//https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/885/

class Solution {
    public int strStr(String haystack, String needle) {
    	if (haystack.length() == needle.length())
            return haystack.equals(needle) ? 0 : -1;

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

        // You don't need to use contains() library since it is overlapped!
        int i = 0, j = 0;
        int start = 0;
        int count = 0;

        while (i < haystack.length() && j < needle.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
                count++;

            } else { //initialize
                start++;
                i = start;
                j = 0;
                count = 0;
            }

            if (count == needle.length()) return start;
        }
        return -1;
    }
}

Java2

좀 더 모듈화하고, 간단하게 구현할 수 있다.

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack.length() == needle.length())
            return haystack.equals(needle) ? 0 : -1;

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

        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
            if (compare(haystack, i, needle)) return i;
        }

        return -1;
    }

    private boolean compare(String haystack, int startIndex, String needle) {
        for (int i = 0; i < needle.length(); i++) {
            int index = startIndex + i;

            if (haystack.charAt(index) != needle.charAt(index)) {
                return false;
            }
        }

        return true;
    }
}

code3

엄청 간단한 것 중엔 이런 것도 있다;

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle) ;               
    }
}