LeetCode 28. Find the Index of the First Occurrence in a String 자바 문제 풀이

문제

Find the Index of the First Occurrence in a String - LeetCode

문제 해결 방법

• 스트링의 indexOf를 사용하면 한번에 해결이 가능합니다.
• 만약 indexOf를 사용하면 안된다면, substring을 이용해서 로직을 짤수 있습니다.
  1. substring을 이용하여, haystack의 문자열을 needle의 길이만큼 자른다.
  2. 자른 문자열을 비교한다.
  3. 자를 문자열의 인덱스를 한칸 옮긴다.
  4. 이를 반복한다. 만약 자른 문자열의 길이가 needle의 길이보다 짧다면, needle문자열은 존재하지 않으므로 -1을 리턴한다
• 즉, 이문제는 문자열을 자르고 검색할수 있는 능력이 있는지 묻는 문제입니다.

Github Link

https://github.com/eunhanlee/LeetCode_28_FindtheIndexoftheFirstOccurrenceinaString_Solution.git

시간복잡도: O(nm), 공간복잡도: O(1)

class Solution {
    public int strStr(String haystack, String needle) {
        // indexOf() 메서드는 주어진 문자열(haystack) 내에서 지정된 부분 문자열(needle)의 첫 번째 발생 위치를 찾습니다.
        // 찾으면 부분 문자열의 첫 번째 문자의 인덱스를 반환하고, 찾지 못하면 -1을 반환합니다.
        return haystack.indexOf(needle);
    }
}

시간복잡도: O(nm), 공간복잡도: O(1)

class Solution {

    /**
     * 주어진 문자열(haystack)에서 지정된 부분 문자열(needle)의 첫 번째 발생 위치를 찾습니다.
     *
     * @param haystack 검색 대상 문자열
     * @param needle   검색할 부분 문자열
     * @return 부분 문자열이 발견되면 첫 번째 문자의 인덱스,
     *         발견되지 않으면 -1을 반환합니다.
     */
    public int strStr(String haystack, String needle) {
        int end = needle.length();  // 부분 문자열 비교의 끝 인덱스
        int start = 0;              // 부분 문자열 비교의 시작 인덱스

        while (end <= haystack.length()) {
            if (haystack.substring(start, end).equals(needle)) {
                // 시작부터 끝까지의 부분 문자열이 needle과 일치하면
                // 시작 인덱스를 반환하여 첫 번째 발생 위치로 간주합니다.
                return start;
            }

            start++;  // 시작 인덱스를 오른쪽으로 이동합니다.
            end++;    // 끝 인덱스를 오른쪽으로 이동합니다.
        }

        // 부분 문자열이 발견되지 않으면 -1을 반환합니다.
        return -1;
    }
}

• 시간 복잡도에서 n은 haystack의 길이이고, m은 needle의 길이입니다.