🌲 每天打卡一道算法題，既是一個(gè)學(xué)習(xí)過程，又是一個(gè)分享的過程😜 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進(jìn)行解題 🌲 要保持一個(gè)每天都在學(xué)習(xí)的狀態(tài)，讓我們一起努力成為算法大神吧🧐！ 🌲 今天是力扣算法題持續(xù)打卡第15天🎈！
實(shí)現(xiàn) strStr()函數(shù)。
給你兩個(gè)字符串 haystack和 needle，請你在 haystack 字符串中找出 needle字符串出現(xiàn)的第一個(gè)位置（下標(biāo)從 0 開始）。
如果不存在，則返回 -1。
說明:
當(dāng) needle是空字符串時(shí)，我們應(yīng)當(dāng)返回什么值呢？這是一個(gè)在面試中很好的問題。
對于本題而言，當(dāng) needle是空字符串時(shí)我們應(yīng)當(dāng)返回 0 。這與 C 語言的 strstr()以及 Java 的 indexOf() 定義相符。
示例 1 ：
輸入：haystack = "hello" , needle = "ll"
輸出：2
示例 2 ：
輸入：haystack = "aaaaa" , needle = "bba"
輸出：- 1
示例 3 ：
輸入：haystack = "" , needle = ""
輸出：0
提示：
0 <= haystack.length, needle.length <= 5 * 104 haystack 和 needle 僅由小寫英文字符組成 思路解析
我看到題目的第一想法是使用IndexOf直接就可以返回第一個(gè)下標(biāo)了
但是這樣毫無算法可言哈哈，后面也把代碼貼上~
暴力法，使用雙層for循環(huán)，讓字符串needle 與字符串 haystack的所有長度為 m 的子串均匹配一次。
為了減少不必要的匹配，我們每次匹配失敗即立刻停止當(dāng)前子串的匹配，對下一個(gè)子串繼續(xù)匹配。
如果當(dāng)前子串匹配成功，我們返回當(dāng)前子串的開始位置即可。如果所有子串都匹配失敗，則返回 ?1。
代碼：
public int strStr ( string , string )
{
int = haystack. Length, m = needle. Length;
for ( int = 0 ; i + m <= n; i++ )
{
bool = true ;
for ( int = 0 ; j < m; j++ )
{
if ( haystack. Substring ( i + j, 1 ) != needle. Substring ( j, 1 ) )
{
flag = false ;
break ;
}
}
if ( flag)
{
return i;
}
}
return - 1 ;
}
執(zhí)行結(jié)果
通過
執(zhí)行用時(shí)：1373 ms，在所有 C# 提交中擊敗了13.13 % 的用戶
內(nèi)存消耗：38.2 MB，在所有 C# 提交中擊敗了61.91 % 的用戶
復(fù)雜度分析
時(shí)間復(fù)雜度：O ( n * m)
空間復(fù)雜度：O ( 1 )
此方法使用C#的IndexOf方法直接拿到符合條件的索引，體現(xiàn)不出算法的精髓。。
代碼：
public class Solution {
public int StrStr ( string , string )
{
if ( needle == "" )
return 0 ;
int = haystack. IndexOf ( needle) ;
return test;
}
}
執(zhí)行結(jié)果
通過
執(zhí)行用時(shí)：920 ms，在所有 C# 提交中擊敗了30.06 % 的用戶
內(nèi)存消耗：24.3 MB，在所有 C# 提交中擊敗了13.88 % 的用戶
此方法跟C#第一種解題思路一致
代碼：
class Solution {
public int strStr ( String haystack, String needle) {
int n = haystack. length ( ) , m = needle. length ( ) ;
for ( int i = 0 ; i + m <= n; i++ ) {
boolean flag = true ;
for ( int j = 0 ; j < m; j++ ) {
if ( haystack. charAt ( i + j) != needle. charAt ( j) ) {
flag = false ;
break ;
}
}
if ( flag) {
return i;
}
}
return - 1 ;
}
}
執(zhí)行結(jié)果
通過
執(zhí)行用時(shí)：1373 ms，在所有 Java 提交中擊敗了13.03 % 的用戶
內(nèi)存消耗：38.2 MB，在所有 Java 提交中擊敗了61.91 % 的用戶
復(fù)雜度分析
時(shí)間復(fù)雜度：O ( n* m)
空間復(fù)雜度：O ( ( 1 )
思路解析
只能說我還不懂。。從力扣大佬參考過來的！
代碼：
class Solution {
// KMP 算法
// ss: 原串(string) pp: 匹配串(pattern)
public int strStr ( String ss, String pp) {
if ( pp. isEmpty ( ) ) return 0 ;
// 分別讀取原串和匹配串的長度
int n = ss. length ( ) , m = pp. length ( ) ;
// 原串和匹配串前面都加空格，使其下標(biāo)從 1 開始
ss = " " + ss;
pp = " " + pp;
char [ ] s = ss. toCharArray ( ) ;
char [ ] p = pp. toCharArray ( ) ;
// 構(gòu)建 next 數(shù)組，數(shù)組長度為匹配串的長度（next 數(shù)組是和匹配串相關(guān)的）
int [ ] next = new int [ m + 1 ] ;
// 構(gòu)造過程 i = 2，j = 0 開始，i 小于等于匹配串長度 【構(gòu)造 i 從 2 開始】
for ( int i = 2 , j = 0 ; i <= m; i++ ) {
// 匹配不成功的話，j = next(j)
while ( j > 0 && p[ i] != p[ j + 1 ] ) j = next[ j] ;
// 匹配成功的話，先讓 j++
if ( p[ i] == p[ j + 1 ] ) j++ ;
// 更新 next[i]，結(jié)束本次循環(huán)，i++
next[ i] = j;
}
// 匹配過程，i = 1，j = 0 開始，i 小于等于原串長度 【匹配 i 從 1 開始】
for ( int i = 1 , j = 0 ; i <= n; i++ ) {
// 匹配不成功 j = next(j)
while ( j > 0 && s[ i] != p[ j + 1 ] ) j = next[ j] ;
// 匹配成功的話，先讓 j++，結(jié)束本次循環(huán)后 i++
if ( s[ i] == p[ j + 1 ] ) j++ ;
// 整一段匹配成功，直接返回下標(biāo)
if ( j == m) return i - m;
}
return - 1 ;
}
}
鏈接：https: / / leetcode- cn. com/ problems/ implement- strstr/ solution/ shua- chuan- lc- shuang- bai- po- su- jie- fa- km- tb86/
執(zhí)行結(jié)果
通過
執(zhí)行用時(shí)：3 ms，在所有 Java 提交中擊敗了72.84 % 的用戶
內(nèi)存消耗：38.5 MB，在所有 Java 提交中擊敗了29.32 % 的用戶
復(fù)雜度分析
時(shí)間復(fù)雜度：O ( m+ n)
空間復(fù)雜度：O ( ( m)
今天是力扣算法題打卡的第十五天！ 文章采用 C#和 Java 兩種編程語言進(jìn)行解題 一些方法也是參考力扣大神寫的，也是邊學(xué)習(xí)邊分享，再次感謝算法大佬們 那今天的算法題分享到此結(jié)束啦，明天再見！
