28_实现_strStr()

类型：字符串

• 28. 实现 strStr() 💚

  https://leetcode-cn.com/problems/implement-strstr/

  ❓ 实现函数strStr() 用于在字符串 haystack 中找到子串 needle 的出现的位置，未出现则返回 -1

  💡 暴力匹配

  class Solution {
      public int strStr(String haystack, String needle) {
          int n = haystack.length(), m = needle.length();
          for (int i = 0; i + m <= n; i++) {
              boolean flag = true;
              for (int j = 0; j < m; j++) {
                  if (haystack.charAt(i + j) != needle.charAt(j)) {
                      flag = false;
                      break;
                  }
              }
              if (flag) {
                  return i;
              }
          }
          return -1;
      }
  }

  时间复杂度树：O(mn)，m 和 n 分别是 haystack 和 needle 的长度。空间复杂度：O(1)

  💡 KMP 算法

  这个一般不作为面试要求，可以理解原理，作为面试亮点。

  时间复杂度：O(m + n)，空间复杂度：O(n)，n 指 needle 的长度。