LeetCode - Easy - 28. Implement strStr()

客官°小女子只卖身不卖艺 2022-12-27 07:55 119阅读 0赞

## Topic ##

Two Pointers, String

## Description ##

[https://leetcode.com/problems/implement-strstr/][https_leetcode.com_problems_implement-strstr]

Implement strStr().

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

> needle /ˈniːdl/ n.针
> 
> haystack /ˈheɪstæk/ n.干草堆
> 
> **a needle in a haystack**：something that is impossible or extremely difficult to find, especially because the area you have to search is too large（类似中文的“大海捞针”）:
> 
> Finding the piece of paper I need in this huge pile of documents is like looking for/trying to find **a needle in a haystack**。
> 
> [Link][]

**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().

**Example 1**:

Input: haystack = "hello", needle = "ll"
    Output: 2

**Example 2**:

Input: haystack = "aaaaa", needle = "bba"
    Output: -1

**Example 3**:

Input: haystack = "", needle = ""
    Output: 0

**Constraints**:

*  0 <= haystack.length, needle.length <= 5 \* 104
 *  haystack and needle consist of only lower-case English characters.

## Analysis ##

方法一：双指针

方法二：KMP算法

## Submission ##

public class ImplementStrStr { 
    	public int strStr(String haystack, String needle) { 
    		
    		for (int i = 0;; i++) { 
    			for (int j = 0;; j++) { 
    				if (j == needle.length())
    					return i;
    				if (i + j == haystack.length())
    					return -1;
    				if (needle.charAt(j) != haystack.charAt(i + j))
    					break;
    			}
    		}
    	}
    	
        private void getNext(int[] next, String s) { 
            int j = -1;
            next[0] = j;
            for(int i = 1; i < s.length(); i++) {  // 注意i从1开始
                while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {  // 前后缀不相同了
                    j = next[j]; // 向前回溯
                }
                if (s.charAt(i) == s.charAt(j + 1)) {  // 找到相同的前后缀
                    j++;
                }
                next[i] = j; // 将j（前缀的长度）赋给next[i]
            }
        }
        
        public int strStr2(String haystack, String needle) { 
            if (needle.length() == 0) { 
                return 0;
            }
            int[] next = new int[needle.length()];
            getNext(next, needle);
            int j = -1; // // 因为next数组里记录的起始位置为-1
            for (int i = 0; i < haystack.length(); i++) {  // 注意i就从0开始
                while(j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {  // 不匹配
                    j = next[j]; // j 寻找之前匹配的位置
                }
                if (haystack.charAt(i) == needle.charAt(j + 1)) {  // 匹配，j和i同时向后移动 
                    j++; 
                }
                if (j == (needle.length() - 1) ) {  // 文本串s里出现了模式串t
                    return (i - needle.length() + 1); 
                }
            }
            return -1;
        }
    	
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class ImplementStrStrTest { 
    
    	@Test
    	public void test() { 
    		ImplementStrStr obj = new ImplementStrStr();
    
    		assertEquals(2, obj.strStr("hello", "ll"));
    		assertEquals(-1, obj.strStr("aaaaaa", "bba"));
    		assertEquals(0, obj.strStr("", ""));
    		assertEquals(-1, obj.strStr("aaa", "aaaa"));
    		
    	}
    	
    	@Test
    	public void test2() { 
    		ImplementStrStr obj = new ImplementStrStr();
    		
    		assertEquals(2, obj.strStr2("hello", "ll"));
    		assertEquals(-1, obj.strStr2("aaaaaa", "bba"));
    		assertEquals(0, obj.strStr2("", ""));
    		assertEquals(-1, obj.strStr2("aaa", "aaaa"));
    		
    	}
    }

[https_leetcode.com_problems_implement-strstr]: https://leetcode.com/problems/implement-strstr/
[Link]: https://dictionary.cambridge.org/us/dictionary/english/a-needle-in-a-haystack#:~:text=a%20needle%20in%20a%20haystack%20meaning%3A%201.%20something,find%2C%20especially%20because%20the%20area%20you%E2%80%A6.%20Learn%20more.