13.字符串查找

描述

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

样例:

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

说明：

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

挑战：

O(n2)的算法是可以接受的。如果你能用O(n)的算法做出来那更加好。（提示：KMP）

代码

时间复杂度O(m * n) m = source.length(), n = target.length()

class Solution {
    public int strStr (String source, String target) {
        if (source == null || target == null) {
        /* 异常条件不写成 source == null || source.length == 0
         * 原因是 source，target 都为空集时应返回 0，不是 -1
         */
            return -1;
        }
        
        // 注意 i 的边界条件中的加 1
        for (int i = 0; i < source.length() - target.length() + 1; i++) {
            // 先定义 j，若仅在 for 循环中定义  j  则后面遇到  j 会报错
            int j = 0;
            for (j = 0; j < target.length(); j++ ) {
                // 满足条件时直接终止内层 for 循环
                if (source.charAt(i + j) != target.charAt(j)) {
                    break;
                }
            } 
            
            if (j == target.length()) {
                return i;
            }
        }
        return -1;
    }
}

Java中length属性是针对数组而言的，而length()方法是针对字符串而言的，size()方法是针对集合而言的