
问题
实现 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 的时间复杂度为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3895。