【小Y學演算法】??每日LeetCode打卡??——15.實作 strStr()

📢前言

• 🌲 每天打卡一道演算法題，既是一個學習程序，又是一個分享的程序😜
• 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
• 🌲 要保持一個每天都在學習的狀態，讓我們一起努力成為演算法大神吧🧐！
• 🌲 今天是力扣演算法題持續打卡第15天🎈！

🌲原題樣例

實作 strStr()函式，

給你兩個字串 haystack和 needle，請你在 haystack 字串中找出 needle字串出現的第一個位置（下標從 0 開始），

如果不存在，則回傳 -1，

說明:

當 needle是空字串時，我們應當回傳什么值呢？這是一個在面試中很好的問題，

對于本題而言，當 needle是空字串時我們應當回傳 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 僅由小寫英文字符組成

🌻C#方法一：暴力法

思路決議

我看到題目的第一想法是使用IndexOf直接就可以回傳第一個下標了

但是這樣毫無演算法可言哈哈，后面也把代碼貼上~

暴力法，使用雙層for回圈，讓字串needle 與字串 haystack的所有長度為 m 的子串均匹配一次，

為了減少不必要的匹配，我們每次匹配失敗即立刻停止當前子串的匹配，對下一個子串繼續匹配，

如果當前子串匹配成功，我們回傳當前子串的開始位置即可，如果所有子串都匹配失敗，則回傳 ?1，

代碼：

    public int strStr(string haystack, string needle)
    {
        int n = haystack.Length, m = needle.Length;
        for (int i = 0; i + m <= n; i++)
        {
            bool flag = true;
            for (int j = 0; j < m; j++)
            {
                if (haystack.Substring(i + j,1) != needle.Substring(j,1))
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                return i;
            }
        }
        return -1;
    }

執行結果

通過
執行用時：1373 ms，在所有 C# 提交中擊敗了13.13%的用戶
記憶體消耗：38.2 MB，在所有 C# 提交中擊敗了61.91%的用戶

復雜度分析

時間復雜度：O(n * m)
空間復雜度：O(1)

🌻C#方法二：傻瓜解法

此方法使用C#的IndexOf方法直接拿到符合條件的索引，體現不出演算法的精髓，，

代碼：

public class Solution {
    public int RemoveElement(int[] nums, int val) {
        if(nums.Length == 0) return 0;
        int count = 0;
        for(int i = 0; i < nums.Length; i++)
            if(nums[i] != val) 
                nums[count++] = nums[i];
        return count;
    }
}

執行結果

通過
執行用時：920 ms，在所有 C# 提交中擊敗了30.06%的用戶
記憶體消耗：24.3 MB，在所有 C# 提交中擊敗了13.88%的用戶

🌻Java 方法一：暴力法

此方法跟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;
    }
}

執行結果

通過
執行用時：1373 ms，在所有 Java  提交中擊敗了13.03%的用戶
記憶體消耗：38.2 MB，在所有 Java 提交中擊敗了61.91%的用戶

復雜度分析

時間復雜度：O(n*m)
空間復雜度：O((1)

🌻Java 方法二： KMP 解法

思路決議

只能說我還不懂，，從力扣大佬參考過來的！

代碼：

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();
        // 原串和匹配串前面都加空格，使其下標從 1 開始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 構建 next 陣列，陣列長度為匹配串的長度（next 陣列是和匹配串相關的）
        int[] next = new int[m + 1];
        // 構造程序 i = 2，j = 0 開始，i 小于等于匹配串長度 【構造 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]，結束本次回圈，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++，結束本次回圈后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接回傳下標
            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/

執行結果

通過
執行用時：3 ms，在所有 Java  提交中擊敗了72.84%的用戶
記憶體消耗：38.5 MB，在所有 Java 提交中擊敗了29.32%的用戶

復雜度分析

時間復雜度：O(m+n)
空間復雜度：O((m)

💬總結

• 今天是力扣演算法題打卡的第十五天！
• 文章采用 C#和 Java 兩種編程語言進行解題
• 一些方法也是參考力扣大神寫的，也是邊學習邊分享，再次感謝演算法大佬們
• 那今天的演算法題分享到此結束啦，明天再見！