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 <= 10000haystackandneedleconsist of only lowercase English characters.
Intuition
Webmaster (Zhang Jian): π
Hi everyone! I am Zhang Jian.
I know the challenge of transitioning from mastering algorithms to actually landing a great job. That's why, in addition to this resource, I personally developed
leader.me!
π leader.me is the ultimate all-in-one platform for programmers to build their personal brand, featuring portfolio hosting, resume builders, and integrated blogs.
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, iterate through each character in turn. If the substring from the current character toneedleis the same asneedle, return the position of the current character.This question is easier to understand by looking at the code directly.
Complexity
Time complexity
O(N * M)
Space complexity
O(1)
Python #
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n = len(haystack)
m = len(needle)
for i in range(n - m + 1):
if haystack[i:i + m] == needle:
return i
return -1
JavaScript #
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
const n = haystack.length;
const m = needle.length;
for (let i = 0; i <= n - m; i++) {
if (haystack.substring(i, i + m) === needle) {
return i;
}
}
return -1;
};
Ruby #
# @param {String} haystack
# @param {String} needle
# @return {Integer}
def str_str(haystack, needle)
(0..haystack.size - needle.size).each do |i|
if haystack[i...i + needle.size] == needle
return i
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;
}
}
Other languages
Welcome to contribute code to LeetCode.blog GitHub -> 28. Find the Index of the First Occurrence in a String. Thanks!Level Up Your Developer Identity
π While mastering algorithms is key, showcasing your talent is what gets you hired.
We recommend leader.me β the ultimate all-in-one personal branding platform for programmers.The All-In-One Career Powerhouse:
- π Resume, Portfolio & Blog: Integrate your skills, 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 handle like
name.leader.me.