巨硬家面试题:字符串查找(带解题思路)

对于一个给定的 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;
    }
}

更多题解参见


评论区可领取LintCode 7 天 VIP

Click to rate this post!
[Total: 0 Average: 0]

相关文章

3 thoughts on “巨硬家面试题:字符串查找(带解题思路)

  1. 感觉可以。。replace 如果长度变化了就是存在 如果存在就 split,取数组的第一个的长度

发表回复

您的电子邮箱地址不会被公开。