28. 实现 strStr()

Posted on Edited on In , ,
转载自Leet Code

题目描述

实现 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() 定义相符。

提示：

  • 0 <= haystack.length, needle.length <= 5 * 10^4
  • haystack 和 needle 仅由小写英文字符组成

我的代码

\(T(N,L)_{worst} = O((N-L)L)\), \(S(N,L) = O(1)\)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MySolution28 
{
    public int strStr(String haystack, String needle) 
    {
    	if (needle==null||needle.length()==0) return 0;
    	else if (haystack==null||needle.length()==0) return -1;
    	
    	for (int i=0; i<haystack.length(); i++)
    	{
    		if (haystack.substring(i).length()<needle.length()) return -1;
    		
    		else if (haystack.charAt(i)==needle.charAt(0)) 
    			if (haystack.substring(i,i+needle.length()).equals(needle))
    				return i;
    	}
    	return -1;
    }
}

时空复杂度：

  • \(T(N,L)_{worst} = O((N-L)L)\)，其中N为haystack串的长度; L为needle串的长度； 内循环中比较子串的复杂度为L, 总共需要比较 (N-L) 次； \(T(N,L)_{best} = O(N)\)。
  • \(S(N,L) = O(1)\).

方法：Rabin Karp - 常数复杂度

\(T(M,N)_{worst} = O(N)\), \(S(M,N) = O(1)\)

首先生成滑窗内子串的哈希码，然后再跟needle的哈希码作比较。 需要解决的问题是：如何在常数时间内生成子串的哈希码？

滚动哈希: 常数时间内生成哈希码

生成一个长度为\(L\)的数组的哈希码，需要\(O(L)\)的时间。 想要在常数时间内生成滑窗数组的哈希码，可以利用滑窗的特性: 每次滑动有一个元素进、一个元素出。

由于只会出现小写英文字母，因此可以将字符串转化成值为0到25的整数数组arr[i]=(int)S.charAt(i)-(int)'a'。 例如，abcd的整数数组形式就是[0, 1, 2, 3]，转换公式如下所示: \[ h_0=0×26^3+1×26^2+2×26^1+3×26^0 \]

将上述公式写成通式如下。其中\(c_i\)为字符串转化而来的整数数组arr中的元素，\(a=26\)为字符集的个数，\(L\)为数组arr的长度。

\[ \begin{aligned} h_0 & = c_0a^{L-1}+c_1a^{L-2}+...+c_ia^{L-1-i}+...+c_{L-1}a^1+c_La^0 \\ & = \sum_{i=0}^{L-1} c_ia^{L-1-i} \end{aligned} \]

接下来考虑窗口从abcd滑动到bcde的情况。 此时，整数数组从[0,1,2,3]变成了[1,2,3,4]，最左边的0被移除，同时最右边新添了4。 滑动后数组的哈希值可以依据滑动前数组的哈希值来计算，公式如下: \[ h_1=(h_0-0×26^3)×26+4×26^0 \]

写成通式如下所示:

\[ h_1=(h_0a-c_0a^L)+c_{L+1} \]

如何避免溢出

\(a^L\)可能是一个很大的数字，因此需要设置数值的上限来避免溢出。 设置数值上限可以采用取模的方式，即用h % modulus来代替原本的哈希值。 理论上，modulus应该取一个很大的数，但是具体应该取多大的数呢？ 详见这篇文章，对于该问题而言\(2^{31}\)就够了。

算法

  • 计算子串haystack.substring(0, L)和needle.substring(0,L)的哈希值;
  • 从起始位置开始遍历到第N-L个字符:
    • 根据前一个哈希值计算滚动哈希;
    • 如果子串哈希值与needle的哈希值相等，则返回滑窗的起始位置;
  • haystack串中不存在needle串，返回-1。

时空复杂度

  • \(T(N,L) = O(N)\)，其中N为haystack串的长度; L为needle串的长度； 计算needle串的哈希值需要\(O(L)\)的时间，之后需要执行\((N-L)\)次循环，每次循环的计算复杂度为常数。
  • \(S(N,L) = O(1)\)。
{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution28 
{
	public int charToInt(int i, String s)
	{
		return (int)s.charAt(i)-(int)'a';
	}
    public int strStr(String haystack, String needle) 
    {
    	int L = needle.length(); int N = haystack.length();
    	if (L>N) return -1;
    	
    	int a = 26; // 滚动哈希的base value: 字符集的个数
    	long modulus = (long)Math.pow(2, 31); // 滚动哈希的modulus value: 避免溢出
    	
    	long hash = 0; long ref_hash = 0;
    	for (int i=0; i<L; i++) // 计算haystack[:L]和needle[:L]的hash值
    	{
    		hash = (hash*a+charToInt(i,haystack)) % modulus;
    		ref_hash = (ref_hash*a+charToInt(i,needle)) % modulus;
    	}
    	if (hash == ref_hash) return 0;
    	
    	long aL = 1; // 常用常量: a**L % modulus
    	for (int i=1; i<=L; i++) aL = (aL*a)%modulus;
    	
    	for (int start=1; start<N-L+1; start++) // 计算滚动哈希（复杂度为常数）
    	{
    		hash = (hash*a-charToInt(start-1,haystack)*aL+charToInt(start+L-1,haystack)) % modulus;
    		if (hash==ref_hash) return start;
    	}
    	
    	return -1;
    }
}