【LeetCode】No.28.ImplementstrStr()JavaVersion

题目链接&＃xff1a; https://leetcode.com/problems/implement-strstr/

1. 题目介绍&＃xff08;strStr()&＃xff09;

Implement strStr().

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

【Translate】&＃xff1a; 给定两个字符串“needle”和“haystack”&＃xff0c;返回“needle”在“haystack”中第一个出现的索引&＃xff0c;如果“needle”不属于“haystack”&＃xff0c;则返回“-1”。

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

【Translate】&＃xff1a; 当指针是空字符串时&＃xff0c;我们应该返回什么?这是一个很好的面试问题。

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

【Translate】&＃xff1a; 对于这个问题&＃xff0c;当needle为空字符串时&＃xff0c;我们将返回0。这与C的strstr()和Java的indexOf()是一致的。

【测试用例】&＃xff1a;

【约束】&＃xff1a;

2. 题解

2.1 indexOf()

  这样的做法无疑就是耍赖了&＃xff0c;因为题目让我实现的就是indexOf()。

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


2.2 Conventional Thinking

  iziang提供的题解 Share my accepted java solution。常规思路了&＃xff0c;把可能的三种情况分别进行了判断。

public int strStr(String haystack, String needle) {int l1 &＃61; haystack.length(), l2 &＃61; needle.length();if (l1 < l2) {return -1;} else if (l2 &＃61;&＃61; 0) {return 0;}int threshold &＃61; l1 - l2;for (int i &＃61; 0; i <&＃61; threshold; i&＃43;&＃43;) {if (haystack.substring(i,i&＃43;l2).equals(needle)) {return i;}}return -1;}


2.3 KMP

   cdai在Accepted KMP solution in java for reference的评论中提供的题解。

// Similar to strStr except compare t against itselfprivate int[] computePrefixFunc(String t) {int[] f &＃61; new int[t.length()];for (int i &＃61; 1, j &＃61; 0; i < t.length(); i&＃43;&＃43;) { // now i &＃61; #matchedwhile (j > 0 && t.charAt(i) !&＃61; t.charAt(j)) j &＃61; f[j - 1];if (t.charAt(i) &＃61;&＃61; t.charAt(j)) j&＃43;&＃43;;f[i] &＃61; j;}return f;}public int strStr(String s, String t) {int[] f &＃61; computePrefixFunc(t);int i, j;for (i &＃61; 0, j &＃61; 0; i < s.length() && j < t.length(); i&＃43;&＃43;) { // never back up iwhile (j > 0 && s.charAt(i) !&＃61; t.charAt(j)) j &＃61; f[j - 1]; // back up j recursively till next char matchif (s.charAt(i) &＃61;&＃61; t.charAt(j)) j&＃43;&＃43;; // if matched move j, otherwise give up current i and move on}return j &＃61;&＃61; t.length() ? i - j : -1;}


3. 可参考

[1] 什么是KMP算法&＃xff08;详解&＃xff09;
[2] KMP算法详解