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

说明

在面试中我是否需要实现 KMP 算法？

• 不需要，当这种问题出现在面试中时，面试官很可能只是想要测试一下你的基础应用能力。当然你需要先跟面试官确认清楚要怎么实现这个题。
• 《九章算法班》中讲过比 KMP 更简单的算法：Rabin-karp 算法

在线做题地址

样例 1:

输入: source = "source" ，target = "target" 输出:-1  样例解释: 如果 source 里没有包含 target 的内容，返回-1  

样例 2:

输入: source = "abcdabcdefg" ，target = "bcd" 输出: 1  样例解释: 如果 source 里包含 target 的内容，返回 target 在 source 里第一次出现的位置  

[题解]

算法：模拟

算法思路

因为本题的时间复杂度比较宽限，不需要更为复杂的 KMP 算法，可以直接模拟，逐一比对每个字符。

代码思路

• 先进行特判，若 target 长度为 0，则返回 0 ；若 target 的长度大于 source，则表示不可能匹配，返回-1
• 枚举匹配 source 的起始位置，从 0 到 sourceLen-targetLen
• 对于一个起始位置，比对之后的 targetLen 位是否相同，若遇到不相同直接退出判断，尝试下一个起始位置
• 当成功比对完 targetLen 位后，说明全部相同，则返回起始位置

复杂度分析

M 表示 source 的长度 N 表示 target 的长度 空间复杂度：O(M+N) 时间复杂度：O(MN)

public class Solution {      /**      * @param source:       * @param target:       * @return: return the index      */      public int strStr(String source, String target) {          //获取两个字符串的长度         int sourceLen = source.length();         int targetLen = target.length();          //注意特判，若 target 长度为 0 则答案为 0         if(targetLen == 0){             return 0;         }          //若 target 长度大于 source，则不可能匹配         if(targetLen > sourceLen){             return -1;         }          for(int i = 0; i < sourceLen-targetLen+1; i++){             //k 表示比对时 source 中所指向的字符             int k = i;             for(int j = 0; j < targetLen; j++){                 if(source.charAt(k) == target.charAt(j)){                     //最后一个字符匹配完成，输出答案                     if(j == targetLen - 1){                         return i;                     }                     k++;                 }                 //其中一个字符无法匹配，直接退出做下一次循环                 else{                     break;                 }             }         }         return -1;     } }  

更多题解参见

大佬有話說 (0)