Поиск максимального общего начального фрагмента в массиве строк

Условие

Метод принимает массив строк и возвращает самый длинный префикс, который присутствует в начале каждой строки массива. Если общего префикса нет, возвращается пустая строка.

Примеры: ["ab", "abc", "abcde", "abf"] → "ab" ["cat", "dog", "bird"] → ""

class Test {
    public String longestPrefix(String[] arr) {
        // TODO
    }
}

Ответ

Постепенно уменьшайте длину префикса первой строки, сравнивая его с каждой следующей. Сортировать массив или создавать промежуточные подстроки на каждом шаге не требуется.

public String longestPrefix(String[] arr) {
    if (arr.length == 0) return "";
    int end = arr[0].length();
    for (int i = 1; i < arr.length && end != 0; i++) {
        end = Math.min(end, arr[i].length());
        int j = 0;
        while (j < end && arr[0].charAt(j) == arr[i].charAt(j)) j++;
        end = j;
    }
    return arr[0].substring(0, end);
}

Контракт предполагает отсутствие null. Время ограничено суммарной длиной входных строк, память O(1) без результата. Одна строка возвращается целиком, пустой массив — пустая строка. Сравнение чувствительно к регистру и использует UTF-16 char.