leetcode28. Implement strStr()

题目描述：

Implement strStr().

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

Example 1:

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

Example 2:

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

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

---

My solution:

思路即为逐个匹配法，将needle与haystack的每一个与needle同长度的子串进行比较，如果匹配，那么返回子串的开始位置，如果所有子串匹配完后都无匹配的子串，那么返回-1。

思路局限：

（1）没有考虑到needle的长度大于haystack的长度。

（2）没有考虑效率问题，与代码简洁问题。

（3）使用了c++中string类的substr方法(该方法原型为sting substr(size_t pos = 0, size_t len = npos) const; )，如何从最底层实现？

int strStr(string haystack, string needle) { if(haystack.empty() && !needle.empty()) return -1; if(haystack.size() < needle.size()) return -1; int i = 0; while( i <= haystack.size() - needle.size()){ if(haystack.substr(i, needle.size()) == needle) return i; i++; } return -1; }

Elegant implementation：

Author:  leetcode ID: jeantimex

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; } }

---