LeetCode 28. Implement strStr()题目分析代码

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

题目

对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。

说明 在面试中我是否需要实现KMP算法？ 不需要，当这种问题出现在面试中时，面试官很可能只是想要测试一下你的基础应用能力。当然你需要先跟面试官确认清楚要怎么实现这个题。

样例 如果 source = "source"和 target = "target"，返回 -1。 如果 source = "abcdabcdefg"和 target = "bcd"，返回 1。

分析

不用kmp算法，用简单的二重循环判断。 首先第一重循环，source的第一位到减去target长度的位数加一（这样是为了处理两个串都是空的情况） 第二重循环，每次都和target的每一位进行比较是否相等，如果找到一位不相等的就直接跳出循环。 最后如果能全部循环完成，就说明这个串是相等的。这样就可以返回所在下标了，也就是i。 这种通过判断不等来判断相等的思想是算法中常用的，需要好好体会掌握

代码

public class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack == null || needle == null)
            return -1;
        int hLen = haystack.length();
        int nLen = needle.length();
        if(hLen == 0 && nLen == 0)
            return 0;
        
        for(int i=0;i<hLen-nLen+1;i++) {
            int j=0;
            for(j=0;j<nLen;j++)
            if(haystack.charAt(i+j) != needle.charAt(j))
                break;
            if(j == nLen)
                return i;
        }
        return -1;
    }
}

Paste_Image.png