leetcode28---實作strStr()

題目描述

實作 strStr() 函數。

給定一個 haystack 字元串和一個 needle 字元串，在 haystack 字元串中找出 needle 字元串出現的第一個位置 (從0開始)。如果不存在，則傳回 -1。

示例 1:

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

輸出: 2

示例 2:

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

輸出: -1

說明:

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

對于本題而言，當 needle 是空字元串時我們應當傳回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。

題解

解法一：

調用Java中String類的indexOf方法直接求解（這題很蛋疼）

複雜度：

時間複雜度：O(1)

空間複雜度：O(1)

代碼實作：

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()){
            return -1;
        }
        if (needle.length() == 0){
            return 0;
        }
        int index = haystack.indexOf(needle);
        return index;
    }
}
           

解法二：

使用基礎算法中的KMP算法求解（不懂的去了解一下KMP算法）

複雜度：

時間複雜度：O(m+n)

空間複雜度：O(n)

代碼實作：

class Solution {
    public int strStr(String str, String ptr ) {
        if(ptr.length() == 0)
            return 0;
        int slen = str.length();
        int plen = ptr.length();
        int[] next = getnext(plen , ptr);
        int k = -1;
        for(int i = 0 ; i < slen ; i++)
        {
            while(k > -1 && str.charAt(i) != ptr.charAt(k+1))
                k = next[k];
            if(ptr.charAt(k+1) == str.charAt(i))
                k++;
            if(k == plen -1)
            {
                return i-plen +1;
            }
        }
        return -1;
        
    }
    
    public int[] getnext(int plen , String ptr )
    {
        int[] next = new int[plen];
        next[0] = -1;//隻有一個字元;
        
        int k = -1;
        
        for(int i = 1 ; i < plen -1 ; i++)
        {
            while(k > -1 && ptr.charAt(k+1) != ptr.charAt(i))
            {
                k = next[k];
            }
            if(ptr.charAt(k+1) == ptr.charAt(i))
            {
                
                k++;
            }
            next[i] = k; 
        }
        return next;
    }
}