C#LeetCode刷题之#28-实现strStr()(Implement strStr())

C#LeetCode刷题之#28-实现strStr()(Implement strStr())

问题

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回  -1。

输入: haystack = “hello”, needle = “ll”

输出: 2

输入: haystack = “aaaaa”, needle = “bba”

输出: -1

说明:

当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

Implement strStr().

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

Input: haystack = “hello”, needle = “ll”

Output: 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().

示例

public class Program {

    public static void Main(string[] args) {
        var haystack = "hello";
        var needle = "ll";

        var res = StrStr(haystack, needle);
        Console.WriteLine(res);

        haystack = "mississippi";
        needle = "issipi";

        res = StrStr2(haystack, needle);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static int StrStr(string haystack, string needle) {
        //利用运行库,无耻的解法
        return haystack.IndexOf(needle);
    }

    private static int StrStr2(string haystack, string needle) {
        //定义匹配变量
        var match = true;
        //从首字母循环,后面的部分无需放在外循环
        //因为内循环可以比较到
        for(var i = 0; i <= haystack.Length - needle.Length; i++) {
            //默认为匹配
            match = true;
            for(var j = 0; j < needle.Length; j++) {
                //使用内循环逐一判定是否每个字母都能匹配
                if(haystack[i + j] != needle[j]) {
                    //发现不匹配时立刻退出内循环
                    match = false;
                    break;
                }
            }
            //如果全部匹配,则直接返回i
            if(match) return i;
        }
        //无法完成匹配
        return -1;
    }

}

以上给出2种算法实现,以下是这个案例的输出结果:

2
-1

分析:

假设2个单词的长度分别为 m 和 n,那么显而易见,StrStr 的时间复杂度基于运行库的实现,StrStr2 的时间复杂度为: O(m*n) 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3895

发表评论

登录后才能评论