Самый длинный общий префикс для n строк

Question

Самый длинный общий префикс для n строк

Даны n строк максимальной длины m. Как найти самый длинный общий префикс, разделяющий хотя бы две строки?

Пример: ['flower', 'flow', 'hello', 'fleet']

Ответ: fl

Я думал построить тройку для всех строк, а затем проверить самый глубокий узел (удовлетворяющий критерию longest), который разветвляется на две/более подстроки (удовлетворяющий критерию commonality). Это займет O(n*m) времени и места. Есть ли лучший способ сделать это

8

algorithm

задан MAK 20 December 2011 в 07:05

1 ответ

Другие вопросы по тегам:

algorithm

Похожие вопросы:

score 0 · Answer 1

Возможно, более интуитивное решение. Направьте уже найденный префикс из более раннего повторения как входная строка к остающемуся или следующему строковому входу. [[[w1, w2], w3], w4]... so on], где [], предположительно, 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;
}