LeetCode编程练习 - Implement strStr()学习心得

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

       实现strStr()。判断一个字符串是否是另一个字符串的子串。

思路：

       遍历字符串中的元素，在前者字符串的长度小于后者字符串的长度的情况下，如果字符串中的元素不相等的话则不是。运行后发现，对于一个字符串确实是另一个字符串的情况下输出结果才是正确的。

       对比解决方案，发现我的思路并不是很清晰，因此在编写上会出现一些问题。假设原字符串的长度为n，匹配字符串的长度为m，原字符串的每一个长度为m的字符串都判断是否跟匹配字符串一致，共有n-m+1个子串，算法时间复杂度为O((n-m+1)*m)=O(n*m)，控件复杂度为O(1)。以heystack作为原字符串，needle作为匹配字符串。i+j为当前的字符串，若当前needle和haystack的字符不同的话则退出，每次匹配不成功i移动一位，而j重新从0 开始，因此haystack的当前位置为i+j。

           还有一种写法，思路相似。以heystack为原字符串，needle为匹配字符串，先判断needle是否和j一样长，若是则直接返回当前匹配的起始位置，表示匹配成功，如果i+j为当前haystack的长度，则表明已经读取完heystack所有字符，并没有匹配成功，若当前needle和haystack的字符不相同则退出。