为什么要使用trie（它需要O(mn)的时间和空间），而不是使用基本的暴力方法。第一次循环，找到最短的字符串minStr，这需要o(n)的时间；第二次循环，与这个minStr逐个比较，并保留一个变量，该变量指示minStr的最右索引，这个循环需要O(mn)的时间，其中m是所有字符串中最短的长度。代码如下所示，
public String longestCommonPrefix(String[] strs) {
if(strs.length==0) return "";
String minStr=strs[0];
for(int i=1;i<strs.length;i++){
if(strs[i].length()<minStr.length())
minStr=strs[i];
}
int end=minStr.length();
for(int i=0;i<strs.length;i++){
int j;
for( j=0;j<end;j++){
if(minStr.charAt(j)!=strs[i].charAt(j))
break;
}
if(j<end)
end=j;
}
return minStr.substring(0,end);
}
使用trie树，可以解决这个问题，时间复杂度为O(|S|*n)。[其中n是字符串数量，S是最长的字符串长度]
(1) put all strings in a trie
(2) do a DFS in the trie, until you find the first vertex with more than 1 "edge".
(3) the path from the root to the node you found at (2) is the longest common prefix.
在大O表示法的意义下，没有可能有更快的解决方案。最坏情况下，假设所有字符串都是相同的，你需要读取它们中的全部内容才能确定。
我会对它们进行排序，这可以在n lg n的时间内完成。然后，具有相同前缀的任何字符串将紧挨着彼此。实际上，您应该能够保持当前查看的索引的指针，并沿着这个指针向下工作，以获得相当快速的计算。
O(m*nlog(n)) 而不是 O(nmlog(nm))，因为正如你所说：比较需要 O(m) 的时间，而这有 O(nlogn) 个，总共需要 O(mnlog(n)) 的时间。 - amitm接近或大于n时，m的概念才是重要的。对于标准英语单词，典型的m将为12或更少。如果考虑非杜撰、非技术性单词，则为33（antidisestablishmentarianistically）。因此，如果您的n是100或更小，它会产生影响，但如果是这种情况，那么您的整个操作都很小，并且O不适用。 O符号用于渐进式评估。 - corsiKa发生的情况是，corsiKa所描述的桶排序（基数排序）可以扩展，以便所有字符串最终都被单独放置在一个桶中，在那个时候，这样一个孤独的字符串的LCP是已知的。此外，每个字符串的shustring也是已知的；它比LCP长一个字符。桶排序实际上是后缀数组的构建，但只有部分。那些未执行的比较（如corsiKa所述）确实代表了那些未添加到后缀数组中的后缀字符串的部分。最后，这种方法不仅允许确定LCP和shustrings，还可以轻松找到那些不存在于字符串中的子序列。
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0)
return "";
char[] c_list = strs[0].toCharArray();
int len = c_list.length;
int j = 0;
for (int i = 1; i < strs.length; i++) {
for (j = 0; j < len && j < strs[i].length(); j++)
if (c_list[j] != strs[i].charAt(j))
break;
len = j;
}
return new String(c_list).substring(0, len);
}
既然世界显然需要一个Swift的答案，那么这就是我的答案；）
func longestCommonPrefix(strings:[String]) -> String {
var commonPrefix = ""
var indices = strings.map { $0.startIndex}
outerLoop:
while true {
var toMatch: Character = "_"
for (whichString, f) in strings.enumerate() {
let cursor = indices[whichString]
if cursor == f.endIndex { break outerLoop }
indices[whichString] = cursor.successor()
if whichString == 0 { toMatch = f[cursor] }
if toMatch != f[cursor] { break outerLoop }
}
commonPrefix.append(toMatch)
}
return commonPrefix
}
Swift 3 更新：
func longestCommonPrefix(strings:[String]) -> String {
var commonPrefix = ""
var indices = strings.map { $0.startIndex}
outerLoop:
while true {
var toMatch: Character = "_"
for (whichString, f) in strings.enumerated() {
let cursor = indices[whichString]
if cursor == f.endIndex { break outerLoop }
indices[whichString] = f.characters.index(after: cursor)
if whichString == 0 { toMatch = f[cursor] }
if toMatch != f[cursor] { break outerLoop }
}
commonPrefix.append(toMatch)
}
return commonPrefix
}
值得注意的是：
鉴于我需要首先编写的函数：
/// Takes an array of Strings representing file system objects absolute
/// paths and turn it into a new array with the minimum number of common
/// ancestors, possibly pushing the root of the tree as many level downwards
/// as necessary
///
/// In other words, we compute the longest common prefix and remove it
func reify(fullPaths:[String]) -> [String] {
let lcp = longestCommonPrefix(fullPaths)
return fullPaths.map {
return $0[lcp.endIndex ..< $0.endIndex]
}
}
这是一个最小化的单元测试：
func testReifySimple() {
let samplePaths:[String] = [
"/root/some/file"
, "/root/some/other/file"
, "/root/another/file"
, "/root/direct.file"
]
let expectedPaths:[String] = [
"some/file"
, "some/other/file"
, "another/file"
, "direct.file"
]
let reified = PathUtilities().reify(samplePaths)
for (index, expected) in expectedPaths.enumerate(){
XCTAssert(expected == reified[index], "failed match, \(expected) != \(reified[index])")
}
}
[[[w1，w2]，w3]，w4] ...等等，其中[]应该是两个字符串的最长公共前缀（LCP）。public String findPrefixBetweenTwo(String A, String B){
String ans = "";
for (int i = 0, j = 0; i < A.length() && j < B.length(); i++, j++){
if (A.charAt(i) != B.charAt(j)){
return i > 0 ? A.substring(0, i) : "";
}
}
// Either of the string is prefix of another one OR they are same.
return (A.length() > B.length()) ? B.substring(0, B.length()) : A.substring(0, A.length());
}
public String longestCommonPrefix(ArrayList<String> A) {
if (A.size() == 1) return A.get(0);
String prefix = A.get(0);
for (int i = 1; i < A.size(); i++){
prefix = findPrefixBetweenTwo(prefix, A.get(i)); // chain the earlier prefix
}
return prefix;
}