[LeetCode] - 28. Find the Index of the First Occurrence in a String

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Find the Index of the First Occurrence in a String" 문제입니다.

--> https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

 

문제 : 

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 <= 10^4 haystack and needle consist of only lowercase English characters.

---

이 문제는 되게 단순합니다. 두 문자열 needle과 haystack이 주어졌을 때, needle이 haystack에 처음 등장하는 인덱스를 반환하고, needle이 haystack에 없으면 -1을 반환하면 됩니다. 자바로 접근할 때, 되게 심플하게 풀 수 있습니다. 코드를 보시죠 : 

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

 

저는 자바가 제공하는 String 메소드를 이용하여 쉽게 이 문제를 해결하였습니다. 간략히 설명을 드리자면, 먼저 haystack이 needle의 string을 포함하는지 안 하는지를 if문으로 확인을 하고, 만약에 있으면 needle이 시작되는 인덱스를 출력하고, 없으면 -1을 출력하는 되게 짧고 간결한 코드로 짰습니다. 

---

제 코드 이외에도 다른 유저들의 답안도 한 번 리뷰해보겠습니다 : 

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) {
            return -1;
        }
        
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            if (haystack.substring(i, i + needle.length()).equals(needle)) {
                return i;
            }
        }
        
        return -1;        
    }
}
// niits 유저의 코드

 

이 분의 코드도 결국에는 저랑 비슷한 아이디어인데요, 요약하자면 이 코드는 : 

• haystack의 길이가 needle의 길이보다 짧으면 -1을 반환합니다.
• haystack의 각 부분 문자열을 순회하며, needle의 길이만큼의 부분 문자열을 추출하여 needle과 비교합니다.
• 부분 문자열이 needle과 일치하면 해당 인덱스를 반환하고, 끝까지 찾지 못하면 -1을 반환합니다.

 

이 유저분의 설명이 정말 친절하고 예시도 들어주십니다, 링크 드리겠습니다 : https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/5349528/video-slicing-approach

---

코드들의 Runtime 결과