Blogs Hub

Implement strStr() - String - Easy - LeetCode - MiniTV

Implement strStr() - String - Easy - LeetCode - मिनी टीवी

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

 

Example 1:

Input: haystack = "hello", needle = "ll"

Output: 2

 

Example 2:

Input: haystack = "aaaaa", needle = "bba"

Output: -1

 

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.String
{
    public class StrStrSoln
    {
        public int StrStr(string haystack, string needle)
        {
            if(haystack == needle)
            {
                return 0;
            }

            if (string.IsNullOrEmpty(haystack))
            {
                return -1;
            }

            if (string.IsNullOrEmpty(needle))
            {
                return 0;
            }

            if(needle.Length > haystack.Length)
            {
                return -1;
            }

            for(int i = 0; i < haystack.Length - needle.Length + 1; i++)
            {
                bool found = true;
                if (haystack[i] == needle[0])
                {
                    for (int j = 1; j < needle.Length; j++)
                    {
                        if(haystack[i+j] != needle[j])
                        {
                            found = false;
                        }
                    }

                    if (found)
                    {
                        return i;
                    }
                }
            }
            return -1;
        }
    }
}

 

Time Complexity: O(n*m) where n is the length of haystack and m is the length of the needle.

Space Complexity: O(1)

 

Unit Tests:

using LeetCode.AskGif.Easy.String;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;

namespace CodingUnitTest.Easy.String
{
    [TestClass]
    public class StrStrSolnTests
    {
        [TestMethod]
        public void StrStrSoln_First()
        {
            var haystack = "hello";
            var needle = "ll";
            var output = 2;
            var res = new StrStrSoln().StrStr(haystack, needle);

            Assert.AreEqual(res, output);
        }

        [TestMethod]
        public void StrStrSoln_Second()
        {
            var haystack = "aaaaa";
            var needle = "bba";
            var output = -1;
            var res = new StrStrSoln().StrStr(haystack, needle);

            Assert.AreEqual(res, output);
        }

        [TestMethod]
        public void StrStrSoln_Third()
        {    
            var haystack = "mississippi";
            var needle = "pi";
            var output = 9;
            var res = new StrStrSoln().StrStr(haystack, needle);

            Assert.AreEqual(res, output);
        }
    }
}