博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
lintcode:strStr 字符串查找
阅读量:5825 次
发布时间:2019-06-18

本文共 1647 字,大约阅读时间需要 5 分钟。

题目:

字符串查找(又称查找子字符串),是字符串操作中一个很有用的函数。你的任务是实现这个函数。

对于一个给定的 source 字符串和一个 target 字符串,你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。

如果不存在,则返回 -1

样例

如果 source = "source" 和 target = "target",返回 -1

如果 source = "abcdabcdefg" 和 target = "bcd",返回 1

挑战

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

说明

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

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

解题:

暴力破解,时间复杂度O(mn)

Java程序:

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;        int sourceLen = source.length();        int targetLen = target.length();        if(targetLen==0)            return 0;        if(targetLen>sourceLen)            return -1;                for(int i=0;i
View Code

总耗时: 1332 ms

Python程序:

class Solution:    def strStr(self, source, target):        # write your code here        if source==None or target ==None:            return -1        if len(target)==0:            return 0         sourcelen = len(source)        targetlen = len(target)        for i in range(sourcelen):            k = i            for j in range(targetlen):                if source[k]==target[j]:                    if j==targetlen-1:                        return i                    k+=1                else:                    break                        return -1
View Code

总耗时: 299 ms

对于应用KMP算法的,待更新

转载地址:http://mlidx.baihongyu.com/

你可能感兴趣的文章
爬虫IP被禁的简单解决方法——切换UserAgent
查看>>
php生成word,并下载
查看>>
紫书 习题8-11 UVa 1615 (区间选点问题)
查看>>
asp.net mvc学习(Vs技巧与Httpcontext)
查看>>
float数据在内存中是怎么存储的
查看>>
dedecms 修改标题长度可以修改数据库
查看>>
Matplotlib学习---用matplotlib画直方图/密度图(histogram, density plot)
查看>>
MySQL案列之主从复制出错问题以及pt-slave-restart工具的使用
查看>>
linux 查看剩余内存数
查看>>
测试人员容易遗漏的隐藏缺陷
查看>>
maven+SpringMVC搭建RESTful后端服务框架
查看>>
[BalkanOI2016]Cruise
查看>>
一本书的摘录
查看>>
重排序(转载)
查看>>
python+selenium之字符串切割操作
查看>>
串结构练习——字符串匹配
查看>>
linux下输入密码不回显
查看>>
《构建之法》读书笔记
查看>>
拿下阿里、头条、滴滴的offer后谈谈面试经验---动身前看一看
查看>>
android开发(49) android 使用 CollapsingToolbarLayout ,可折叠的顶部导航栏
查看>>