面试题:求字符串交集算法

本贴最后更新于 2949 天前,其中的信息可能已经时移世异

判断两个字符串的交集,比如:A="I love China" B="Feng Love Yun" 它们的交集为"love",请写出一个算法找出它。(写出伪代码或者思路即可)。

这道题我直接懵比了,求大神给个思路。。

-----------------------------分割线----------------------------------
更新:
参照网上的例子,自己写出了程序,运行成功,不知算不算优化。。
参照链接

自己的代码:

import java.util.ArrayList; import java.util.List; /** * 字符串求交集算法:求两个字符串中的最大交集 * 例如:A="I love China", B="Feng Love Yun",它们的最大交集为“love”(忽略大小写) * 1。 取较短字符串跟较长字符串比较 * 2。 讲较短字符串穷举(由长到短穷举),用更小的字符串去跟较长字符串比较 * 3. 直到找到第一个匹配的子串时返回 * * Created on 2017/5/13. * @author pangwen * @version 0.1 */ public final class StringIntersection { private StringIntersection() { throw new IllegalAccessError("cannot create instance."); } public static String getIntersection(String a, String b, boolean ignorecase) { if (null == a || null == b || a.trim().equals("") || b.trim().equals("")) throw new IllegalArgumentException("字符串不能为空串!"); //如果忽略大小写则将字符串统一转化为小写 if (ignorecase) { a = a.toLowerCase(); b = b.toLowerCase(); } String result; if (a.length() < b.length()) { //穷举a串的子串跟b比较 result = compile(a, b); } else { //穷举b的子串跟a比较 result = compile(b, a); } return result; } private static String compile(String a, String b) { String result = ""; flag: for (int i = 0; i < a.length(); i++) { List substrList = getSubstrList(a, i); for (String str : substrList) { if (b.contains(str)) { result = str; break flag; } } } return result; } private static List getSubstrList(String str, int num) { List substrList = new ArrayList<>(); if (num == 0) { substrList.add(str); return substrList; } int len = str.length(); //第一个子串 substrList.add(str.substring(0, len - num)); //中间子串 for (int j = 1; j < num; j++) { substrList.add(str.substring(j, len - (num - j))); } //最后一个子串 substrList.add(str.substring(num)); return substrList; } public static void main(String[] args) { String a = "I love China", b = "Feng Love Yun"; long start = System.currentTimeMillis(); String intersection = getIntersection(a, b, true); long end = System.currentTimeMillis(); System.out.println(intersection.trim() + "----> 耗时:"+(end -start)+"ms"); } }
  • 面试

    面试造航母,上班拧螺丝。多面试,少加班。

    326 引用 • 1395 回帖
  • 算法
    423 引用 • 254 回帖 • 24 关注
  • 字符串
    30 引用 • 57 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • OpenCV
    15 引用 • 36 回帖 • 7 关注
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    284 引用 • 248 回帖 • 1 关注
  • GAE

    Google App Engine(GAE)是 Google 管理的数据中心中用于 WEB 应用程序的开发和托管的平台。2008 年 4 月 发布第一个测试版本。目前支持 Python、Java 和 Go 开发部署。全球已有数十万的开发者在其上开发了众多的应用。

    14 引用 • 42 回帖 • 819 关注
  • Chrome

    Chrome 又称 Google 浏览器,是一个由谷歌公司开发的网页浏览器。该浏览器是基于其他开源软件所编写,包括 WebKit,目标是提升稳定性、速度和安全性,并创造出简单且有效率的使用者界面。

    63 引用 • 289 回帖
  • 强迫症

    强迫症(OCD)属于焦虑障碍的一种类型,是一组以强迫思维和强迫行为为主要临床表现的神经精神疾病,其特点为有意识的强迫和反强迫并存,一些毫无意义、甚至违背自己意愿的想法或冲动反反复复侵入患者的日常生活。

    15 引用 • 161 回帖 • 5 关注
  • 生活

    生活是指人类生存过程中的各项活动的总和,范畴较广,一般指为幸福的意义而存在。生活实际上是对人生的一种诠释。生活包括人类在社会中与自己息息相关的日常活动和心理影射。

    229 引用 • 1432 回帖 • 1 关注
  • Ubuntu

    Ubuntu(友帮拓、优般图、乌班图)是一个以桌面应用为主的 Linux 操作系统,其名称来自非洲南部祖鲁语或豪萨语的“ubuntu”一词,意思是“人性”、“我的存在是因为大家的存在”,是非洲传统的一种价值观,类似华人社会的“仁爱”思想。Ubuntu 的目标在于为一般用户提供一个最新的、同时又相当稳定的主要由自由软件构建而成的操作系统。

    127 引用 • 169 回帖 • 1 关注
  • SQLServer

    SQL Server 是由 [微软] 开发和推广的关系数据库管理系统(DBMS),它最初是由 微软、Sybase 和 Ashton-Tate 三家公司共同开发的,并于 1988 年推出了第一个 OS/2 版本。

    21 引用 • 31 回帖
  • Dubbo

    Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 614 关注
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    7 引用 • 27 回帖 • 1 关注
  • Telegram

    Telegram 是一个非盈利性、基于云端的即时消息服务。它提供了支持各大操作系统平台的开源的客户端,也提供了很多强大的 APIs 给开发者创建自己的客户端和机器人。

    5 引用 • 35 回帖 • 1 关注
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    588 引用 • 3528 回帖 • 1 关注
  • Latke

    Latke 是一款以 JSON 为主的 Java Web 框架。

    71 引用 • 535 回帖 • 834 关注
  • Mobi.css

    Mobi.css is a lightweight, flexible CSS framework that focus on mobile.

    1 引用 • 6 回帖 • 763 关注
  • Follow
    4 引用 • 12 回帖 • 5 关注
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 692 关注
  • VirtualBox

    VirtualBox 是一款开源虚拟机软件,最早由德国 Innotek 公司开发,由 Sun Microsystems 公司出品的软件,使用 Qt 编写,在 Sun 被 Oracle 收购后正式更名成 Oracle VM VirtualBox。

    10 引用 • 2 回帖 • 16 关注
  • Elasticsearch

    Elasticsearch 是一个基于 Lucene 的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于 RESTful 接口。Elasticsearch 是用 Java 开发的,并作为 Apache 许可条款下的开放源码发布,是当前流行的企业级搜索引擎。设计用于云计算中,能够达到实时搜索,稳定,可靠,快速,安装使用方便。

    117 引用 • 99 回帖 • 199 关注
  • 负能量

    上帝为你关上了一扇门,然后就去睡觉了....努力不一定能成功,但不努力一定很轻松 (° ー °〃)

    89 引用 • 1251 回帖 • 397 关注
  • 架构

    我们平时所说的“架构”主要是指软件架构,这是有关软件整体结构与组件的抽象描述,用于指导软件系统各个方面的设计。另外还有“业务架构”、“网络架构”、“硬件架构”等细分领域。

    142 引用 • 442 回帖 • 3 关注
  • IDEA

    IDEA 全称 IntelliJ IDEA,是一款 Java 语言开发的集成环境,在业界被公认为最好的 Java 开发工具之一。IDEA 是 JetBrains 公司的产品,这家公司总部位于捷克共和国的首都布拉格,开发人员以严谨著称的东欧程序员为主。

    181 引用 • 400 回帖
  • 微信

    腾讯公司 2011 年 1 月 21 日推出的一款手机通讯软件。用户可以通过摇一摇、搜索号码、扫描二维码等添加好友和关注公众平台,同时可以将自己看到的精彩内容分享到微信朋友圈。

    133 引用 • 796 回帖
  • GitLab

    GitLab 是利用 Ruby 一个开源的版本管理系统,实现一个自托管的 Git 项目仓库,可通过 Web 界面操作公开或私有项目。

    46 引用 • 72 回帖
  • 支付宝

    支付宝是全球领先的独立第三方支付平台,致力于为广大用户提供安全快速的电子支付/网上支付/安全支付/手机支付体验,及转账收款/水电煤缴费/信用卡还款/AA 收款等生活服务应用。

    29 引用 • 347 回帖 • 1 关注
  • Hexo

    Hexo 是一款快速、简洁且高效的博客框架,使用 Node.js 编写。

    22 引用 • 148 回帖 • 8 关注
  • OneDrive
    2 引用 • 3 关注
  • gRpc
    11 引用 • 9 回帖 • 98 关注