[LeetCode 28] 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.

Hint

---

Hint 1

  The problem statement clearly asks us to modify the array in-place and it also says that the element beyond the new length of the array can be anything. Given an element, we need to remove all the occurrences of it from the array. We don't technically need to **remove** that element per se, right?
	

Hint 2

  We can move all the occurrences of this element to the end of the array. Use two pointers!
	

Hint 3

  Yet another direction of thought is to consider the elements to be removed as non-existent. In a single pass, if we keep copying the visible elements in-place, that should also solve this problem for us.
	

Code

---

내 제출

---

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack.contains(needle)) {
            //bw.write(String.valueOf(haystack.indexOf("sad")));
            return haystack.indexOf(needle);
        } else {
            //bw.write("false");
            return -1;
        }
    }
}

Runtime	Memory
0 ms	41.8 MB

다른 풀이

---

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();

        if (m == 0) return 0;

        for (int i = 0; i <= n - m; i++) {
            int j = 0;

            while (j < m && haystack.charAt(i + j) == needle.charAt(j)) {
                j++;
            }

            if (j == m) return i;
        }

        return -1;
    }
}

Reference

---