Определение наибольшего общего префикса строки

Условие

Дан массив строк. Требуется реализовать метод, который возвращает самый длинный префикс, одинаковый для всех элементов массива. Если такого префикса нет, метод должен вернуть пустую строку.

Пример 1: ["тест", "тестуюаубауб", "тестфыв", "тест1"] → "тест"

Пример 2: ["юцу", "авро", "кеквао"] → ""

class Task {
    public String longestCommonPref(String[] words) {
        return "";
    }
}

Ответ

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

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

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