Implement strstr in the language of your choice.

Question

Tim · Accepted Answer

Here is an idea:

public static class StringExtensions
    {
        public static int StrStr(this string original, string target)
        {
            int indexOriginal = 0;
            int indexTarget = 0;

            if (target.Length == 0)
            {
                return -1;
            }

            while (indexOriginal  0)
                    {
                        indexOriginal--;
                        indexTarget = 0;
                    }
                }
                else
                {
                    indexTarget++;
                }

                if (indexTarget == target.Length)
                {
                    return indexOriginal - indexTarget + 1;
                }

                indexOriginal++;
            }

            return -1;
        }
    }

Anuj · Answer

The code you written is O(m n). Try something O(m) where m is the string length, and n is the pattern length which needs to be searched. Try using KMP method.

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas