leetcode 28. Implement strStr() 三种解法

朱雀 2022-07-19 01:26 132阅读 0赞

###  ###

# 28. Implement strStr() #

Question Editorial Solution

[My Submissions][]

*  Total Accepted: 119996
 *  Total Submissions: 467056
 *  Difficulty: Easy

Implement strStr().

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

## 作弊解法： ##

public class Solution {
        public int strStr(String haystack, String needle) {
            return haystack.indexOf(needle);
        }
    }

## 子串匹配解法： ##

public class Solution {
        public int strStr(String haystack, String needle) {
            int l1 = haystack.length(), l2 = needle.length();
            if (l1 < l2) {
                return -1;
            } else if (l2 == 0) {
                return 0;
            }
            int threshold = l1 - l2;
            for (int i = 0; i <= threshold; ++i) {
                if (haystack.substring(i,i+l2).equals(needle)) {
                    return i;
                }
            }
            return -1;
        }
    }

### KMP解法：（真的解法） ###

public String strStr(String haystack, String needle) {
    	//KMP algorithms
    	if(needle.equals("")) return haystack;
    	if(haystack.equals("")) return null;
    	char[] arr = needle.toCharArray();
    	int[] next = makeNext(arr);
    
    	for(int i = 0, j = 0, end = haystack.length(); i < end;){
    		if(j == -1 || haystack.charAt(i) == arr[j]){
    			j++;
    			i++;
    			if(j == arr.length) return haystack.substring(i - arr.length);
    		}
    		if(i < end && haystack.charAt(i) != arr[j]) j = next[j];
    	}
        return null;
    }
    
    private int[] makeNext(char[] arr){
    	int len = arr.length;
    	int[] next = new int[len];
    
    	next[0] = -1;
    	for(int i = 0, j = -1; i + 1 < len;){
    		if(j == -1 || arr[i] == arr[j]){
    			next[i+1] = j+1;
    			if(arr[i+1] == arr[j+1]) next[i+1] = next[j+1];
    			i++;
    			j++;
    		}
    		if(arr[i] != arr[j]) j = next[j];
    	}
    
    	return next;

[My Submissions]: https://leetcode.com/problems/implement-strstr/submissions/