Problem

Submissions

Hints & solutions

Discuss

Implement strStr()

Moderate

0/80

Average time to solve is 25m

Contributed by

12 upvotes

Asked in companies

Problem statement

You are given two strings A and B. Find the index of the first occurrence of A in B. If A is not present in B, then return -1.

For Example:

A = “bc”, B = “abcddbc”.
String “A” is present at index 1, and 5(0-based index), but we will return 1 as it is the first occurrence of “A” in string “B”.

Follow Up:

Can you solve this in linear time and space complexity?

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case contains two strings A and B, separated by a single space.

Output format:

For each test case, print the index of the first occurrence of A in B, if string A is not present in string B then print -1.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= |A|, |B| <= 5 * 10^4 

Time limit: 1 second

Sample Input 1:

2
ninjas codingninjas
code codingninjas

Sample Output 1:

6
-1

Explanation For Sample Input 1:

For the first test case, “ninjas” is present at the 6th index of “codingninjas”.

For the second test case, “code” is not present in “codingninjas”.

Sample Input 2:

2
e add
en engagement

Sample output 2:

-1
0

Hint 1

Hint 2

Think of brute force solution by traversing the string B and checking for the occurrence of A.

Approaches (2)

Approach 1

Approach 2

Brute-force

If the length of B is less than the length of A, then we simply return -1.
Now let’s denote the length of A as M and the length of B as N.
Now, we run a loop from 0 to N - M and for each index i in the range of 0 to N - M, we run another loop from 0 to M. Let’s denote this inner loop counter as j.
Then match the characters at (i + j)th index of B with (j)th index of A. If at any point characters mismatch, then we break the inner loop and increment i by 1. If all these characters match, and we are out of the inner loop, then we return i, as it is the index of the first occurrence of A in B.
If we reach at the end of the outer loop, then we return -1, as A is not present in B.

Time Complexity

O(N * M), where N is the length of the string B and M is the length of string A.

In the worst case, we will be traversing the whole string B, and for each index of B, we will traverse the string A. Hence the time complexity is O(N * M).

Space Complexity

O(1).

Constant extra space is required.

(100% EXP penalty)

Implement strStr()

Console