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

数据结构和算法►字符串 , , 评论

来源:

lintcode-最常公共前缀

描述

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

样例

1
2
3
在 "ABCD" "ABEF" 和 "ACEF" 中,  LCP 为 "A"

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

解题思路

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

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

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

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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

更多学习笔记见个人博客——>呼延十

呼延十Developer

个人简介。