大数据

LintCode 字符串查找

题目

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

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

样例
如果 source = “source”和 target = “target”,返回 -1。
如果 source = “abcdabcdefg”和 target = “bcd”,返回 1。

分析

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

代码

class Solution {
    /**
     * Returns a index to the first occurrence of target in source,
     * or -1  if target is not part of source.
     * @param source string to be scanned.
     * @param target string containing the sequence of characters to match.
     */
    public int strStr(String source, String target) {
        //write your code here
        if (source == null || target == null) {
            return -1;
        }

        for(int i = 0; i < source.length() - target.length() + 1; i++)
        {
            int j = 0;
            for(j = 0; j < target.length(); j++)
            {
                if(source.charAt(i+j) != target.charAt(j))
                    break;
            }
            if(j == target.length())
                return i;
        }
        return -1;
    }
}