[每日一题]最常公共前缀

来源:

lintcode-最常公共前缀

描述

给k个字符串,求出他们的最长公共前缀(LCP)

样例

在 "ABCD" "ABEF" 和 "ACEF" 中,  LCP 为 "A"

在 "ABCDEFG", "ABCEFG", "ABCEFA" 中, LCP 为 "ABC"

解题思路

这道题可以很轻易的想到两个思路.

  1. 两两比较,即第一个和第二个拿到公共前缀,在用公共前缀去和第三个取公共前缀….
  2. 拿第一个的每个字符去和其余的所有字符串在该位置的字符比较,相同则继续下一个字符,有一个字符串不相同则结束.

下面是第二种思路的实现代码.

实现代码

public String longestCommonPrefix(String[] strs) {
  // 输入为空
  if (strs.length == 0) {
    return "";
  }
  //取最短的字符串为遍历字符串
  for (int i = 1; i < strs.length; i++) {
    if (strs[0].length() > strs[i].length()) {
      String tmp = strs[0];
      strs[0] = strs[i];
      strs[i] = tmp;
    }
  }
  //如果最短的字符串为空,返回空
  if (strs[0].length() == 0) {
    return "";
  }

  int j = 0;
  for (; j < strs[0].length(); j++) {
    if (!isAllSame(strs, j)) {
      break;
    }
  }

  return strs[0].substring(0, j);
}

/**
 * 判断所有字符串在index位置的字符串是否相同
 */
private boolean isAllSame(String[] strs, int index) {
  char c = strs[0].charAt(index);
  for (String str : strs) {
    if (str.charAt(index) != c) {
      return false;
    }
  }
  return true;
}

注意事项

实现代码中,可以选择不做”排序”,随便拿一个字符串当做遍历的标杆都可以.但是需要遍历检查字符串不为空.

上述思路是取到最短的字符串,一来可以减少遍历次数,二来可以方便的进行判空.

ChangeLog

2018-12-09 完成

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com


本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券