Longest Common Prefix

Условие

Необходимо найти самый длинный общий префикс среди массива строк. Если общего префикса нет, вернуть пустую строку "".

Примеры

Input: ["flower", "flow", "flight"]

Output: "fl”

Input: ["dog", "racecar", "car"]

Output: "”

Explanation: Среди входных строк нет общего префикса.

Решение

fun longestCommonPrefix(strs: Array<String>): String {
    if (strs.isEmpty()) return "" // Если массив пуст, сразу возвращаем пустую строку

    var prefix = strs[0] // Начинаем с первой строки как потенциального общего префикса

    // Проходим по каждой строке массива, начиная со второй
    for (i in 1 until strs.size) {
        // Пока текущая строка не содержит префикс, укорачиваем префикс
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length - 1)
            if (prefix.isEmpty()) return ""  // Если префикс стал пустым, возвращаем пустую строку
        }
    }

    return prefix  // Возвращаем итоговый общий префикс
}

Временная сложность

O(n), где n — это общее количество символов во всех строках. В худшем случае алгоритм должен сравнить все символы всех строк.

Пространственная сложность

O(1), так как мы используем постоянное количество дополнительной памяти, не считая входных данных.