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

    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

    • 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 our GitHub repository, thanks! The location of this solution is 28. Find the Index of the First Occurrence in a String.
    PreviousNext