描述

实现时间复杂度为 O(n + m)的方法 strStr 。 strStr 返回目标字符串在源字符串中第一次出现的第一个字符的位置. 目标字串的长度为 m , 源字串的长度为 n . 如果目标字串不在源字串中则返回 -1 。

在线评测地址

样例 1

输入：source = "abcdef"，target = "bcd" 输出：1 解释： 字符串第一次出现的位置为 1 。 

样例 2

输入：source = "abcde"，target = "e" 输出：4 解释： 字符串第一次出现的位置为 4 。 

算法：HASH

• 字符串 Hash 可以通俗的理解为，把一个字符串转换为一个整数。
• 如果我们通过某种方法，将字符串转换为一个整数，就可以快速的判断两个字符串是否相同。
• 当然如果有不同的两个字符串同时 Hash 到一个整数，这样就比较麻烦了，所以我们希望构造这个 Hash 函数使得他们成为一个单射。

算法思路

• 给定一个字符串 S,对于一个字符 c 我们规定 id(c)=c-‘a’+1
• hash[i]=(hash[i-1]*p+id(s[i]))%MOD
• p 和 MOD 均为质数，并且要尽量大

代码思路

1. 计算 target 的 hash 值
2. 计算 source 的 hash 值的过程中，依次计算每 targetLen 位的 hash 值。
   

   假设 target 长度为 2，source 为“abcd”

   hash(“cd”) = (hash(“bc + d”) – hash(“b”)*2 ) % BASE

复杂度分析

N 表示字符串 source 长度，M 表示字符串 target 长度

• 空间复杂度：O(1)
• 时间复杂度：O(N+M)

public class Solution {      private static final Integer BASE = 100007;      /*       * @param source: A source string       * @param target: A target string       * @return: An integer as index       */      public int strStr2(String source, String target) {          if (source == null || target == null) {              return -1;          }                    int m = target.length();          if (m == 0) {              return 0;          }                    int power = 1;          for (int i = 0; i < m; i++) {              power = (power * 31) % BASE;          }          //先计算一下 target 的 hash 值          int targetCode = 0;          for (int i = 0; i < m; i++) {              targetCode = (targetCode * 31 + target.charAt(i)) % BASE;          }          //当 source code 加上右边一个 character，就要减掉左边的一个 character          int sourceCode = 0;          for (int i = 0; i < source.length(); i++) {              sourceCode = (sourceCode * 31 + source.charAt(i)) % BASE;              if (i <= m - 1) {                  continue;              }                            sourceCode = (sourceCode - power * source.charAt(i - m)) % BASE;              if (sourceCode < 0) {                  sourceCode += BASE;              }              //若 hash 值相同，返回答案              if (sourceCode == targetCode) {                  return i - m + 1;              }          }          return -1;      }  } 

更多题解参考

大佬有話說 (0)