[Easy] LeetCode - no.28 Find the Index of the First Occurrence in a String : Java

https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

needle이라는 단어가 haystack에 나타나지 않는다면 -1을 반환, 나타난다면 처음으로 나타나는 곳의 인덱스를 반환

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.

 

 

 

풀이

class Solution {
    public int strStr(String haystack, String needle) {
        if (!haystack.contains(needle)) {
            return -1;
        }

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

        return -1;
    }
}

• haystack이 needle을 포함하지 않는다면 -1 반환
• for문을 통해 haystack을 차근차근 substring()한 후 needle과 비교 -> 일치 시 i값 리턴
• 시간복잡도 : O(N * M) (N은 haystack의 길이, M은 needle의 길이)