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

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

判断两个字符串的交集,比如: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");
}
}
  • 面试

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

    317 引用 • 1390 回帖 • 8 关注
  • 算法
    375 引用 • 252 回帖 • 20 关注
  • 字符串
    28 引用 • 57 回帖

相关帖子

欢迎来到这里!

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

注册 关于
请输入回帖内容 ...
  • pangwen
    捐赠者 作者

    ... 是的,直接粘贴上来,然后全选后 Tab 一下。。。

  • 其他回帖
  • ht09qwe

    感觉你的代码排版很有问题

    1 回复
  • bk201

    字符串一 char 字符放入 list 然后对 list 做交集处理

    1 回复
  • feix 1 赞同

    看完题第一反应就是对 A/B 拆词后匹配另一个。。。貌似这不是算法~ 如果不能保证有语义的词汇,那就匹配字符咯。AB 两个串都构造一个 int[26],然后分别遍历字符,按照英文字母顺序匹配。契合了相应位置加 1.然后比对两个数组。一起不为 0 的就是交集。 😆

    1 回复
  • 查看全部回帖