LeetCode Python/Java/C++/JS  >  String  >  28. Find the Index of the First Occurrence in a String  >  Solved in Python, JavaScript, Ruby, C++, Java, Go, C#  >  GitHub or Repost

    LeetCode link: 28. Find the Index of the First Occurrence in a String, difficulty: Easy.

    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 <= 10000
    • haystack and needle consist of only lowercase English characters.

    Intuition
    PreviousNext

    πŸš€ While mastering algorithms is key, showcasing your talent is what gets you hired.
    We recommend Show.dev β€” the ultimate all-in-one personal branding platform for programmers.


    • This kind of question can be solved with one line of code using the built-in index(). Obviously, the questioner wants to test our ability to control the loop.

    • For heystack, traverse each character in turn. There may be two situations:

      1. First, the character is not equal to the first letter of needle. Then process the next character.
      2. Second, if the character is equal to the first letter of needle, continue to compare the next character of heystack and needle in an internal loop until they are not equal or needle has completely matched.

    • This question is easier to understand by looking at the code directly.

    Complexity

    Time complexity

    O(N + M)

    Space complexity

    O(1)

    Solution in languages: Python JavaScript Ruby C++ Java Go C#

    Python # 

    class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack)):
            j = 0

            while i + j < len(haystack) and haystack[i + j] == needle[j]:
                j += 1

                if j == len(needle):
                    return i

        return -1

    JavaScript # 

    var strStr = function (haystack, needle) {
  for (let i = 0; i < haystack.length; i++) {
    let j = 0

    while (i + j < haystack.length && haystack[i + j] == needle[j]) {
        j += 1

        if (j == needle.length) {
            return i
        }
    }
  }

  return -1
};

    Ruby # 

    # @param {String} haystack
# @param {String} needle
# @return {Integer}
def str_str(haystack, needle)
  (0...haystack.length).each do |i|
    j = 0

    while i + j < haystack.length && haystack[i + j] == needle[j]
      j += 1

      return i if j == needle.length
    end
  end

  -1
end

    C++ # 

    class Solution {
public:
    int strStr(string haystack, string needle) {
        for (int i = 0; i < haystack.length(); i++) {
            int j = 0;

            while (i + j < haystack.length() && haystack[i + j] == needle[j]) {
                j++;

                if (j == needle.length()) {
                    return i;
                }
            }
        }

        return -1;
    }
};

    Java # 

    class Solution {
    public int strStr(String haystack, String needle) {
        for (int i = 0; i < haystack.length(); i++) {
            int j = 0;

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

                if (j == needle.length()) {
                    return i;
                }
            }
        }

        return -1;
    }
}

    Go # 

    func strStr(haystack string, needle string) int {
    for i := 0; i < len(haystack); i++ {
        j := 0

        for i+j < len(haystack) && haystack[i+j] == needle[j] {
            j++

            if j == len(needle) {
                return i
            }
        }
    }

    return -1
}

    C# # 

    public class Solution {
    public int StrStr(string haystack, string needle) {
        for (int i = 0; i < haystack.Length; i++) {
            int j = 0;

            while (i + j < haystack.Length && haystack[i + j] == needle[j]) {
                j++;

                if (j == needle.Length) {
                    return i;
                }
            }
        }

        return -1;
    }
}
    Solution in languages: Python JavaScript Ruby C++ Java Go C#

    Other languages

    Welcome to contribute code to LeetCode.blog GitHub -> 28. Find the Index of the First Occurrence in a String. Thanks!
    PreviousNext

    Level Up Your Developer Identity

    πŸš€ While mastering algorithms is key, showcasing your talent is what gets you hired.
    We recommend Show.dev β€” the ultimate all-in-one personal branding platform for programmers.

    The All-In-One Career Powerhouse:

    • πŸ“„ Resume, Portfolio & Blog: Integrate your skills, GitHub projects, and writing into one stunning site.
    • 🌐 Free Custom Domain: Bind your own personal domain for freeβ€”forever.
    • ✨ Premium Subdomains: Stand out with elite tech handles like name.cto.page or name.engineer.dev.
    • πŸ”— Cool Short Links: Get sleek, memorable bio-links like is.bio/yourname and an.dev/yourname.

    Build Your Programmer Brand at Show.dev β†’