Ссылка на задачу

Напишите функцию для поиска самой длинной строки с общим префиксом среди массива строк.

Если общего префикса нет, верните пустую строку "".

Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Решение на Java

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 1) {
            return strs[0];
        }

        Arrays.sort(strs);

        for(int i = 0; i < strs[0].length(); i++) {
            if (strs[0].charAt(i) != strs[strs.length-1].charAt(i)) {
                return strs[0].substring(0, i);
            }
        }

        return strs[0];
    }
}

Объяснение

Этот код находит самую длинную общую начальную часть (префикс) среди всех строк в массиве строк. Например, для строк ["flower", "flow", "flight"] общий префикс будет "fl".

Как это работает?

  1. Проверка на единственную строку:

    if(strs.length == 1) {
    return strs[0];
}

    Если в массиве только одна строка, то она сама является общим префиксом.

  2. Сортировка массива строк:

    Arrays.sort(strs);

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

  3. Проход по символам первой строки и сравнение с последней строкой:

    for(int i = 0; i < strs[0].length(); i++) {
    if (strs[0].charAt(i) != strs[strs.length-1].charAt(i)) {
        return strs[0].substring(0, i);
    }
}
    • Проходим по символам первой строки (которая после сортировки станет самой “маленькой” в алфавитном порядке).
    • Если находим символ, который не совпадает с символом на той же позиции в последней строке (самой “большой” после сортировки), то возвращаем часть первой строки до этого символа.

  4. Возврат первой строки, если все символы совпали:

    return strs[0];

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

Пример:

Рассмотрим массив строк ["flower", "flow", "flight"]:

  1. Проверка: массив не содержит одну строку.
  2. Сортируем массив: ["flight", "flow", "flower"].
  3. Берем первую строку “flight” и последнюю “flower”.
  4. Сравниваем символы:
    • i = 0, f == f
    • i = 1, l == l
    • i = 2, i != o
  5. Возвращаем результат до первой несовпадающей позиции: "fl".

Решение на Ruby

# @param {String[]} strs
# @return {String}
def longest_common_prefix(strs)
    return strs[0] if strs.size == 1

    strs.sort!

    strs[0].chars.each_with_index do |ch, i|
        return strs[0][0...i] if ch != strs.last[i]
    end

    strs[0]
end

Решение на Golang

func longestCommonPrefix(strs []string) string {
    if len(strs) == 1 {
        return strs[0]
    }

    sort.Strings(strs)

    n := len(strs) - 1
    for i := range strs[0] {
        if strs[0][i] != strs[n][i] {
            return strs[0][:i]
        }
    }

    return strs[0]
}

Решение на Javascript / Typescript

function longestCommonPrefix(strs: string[]): string {
        if (strs.length === 1) {
            return strs[0];
        }

        strs.sort();

        for (let i = 0; i < strs[0].length; i++) {
            if (strs[0].charAt(i) !== strs[strs.length - 1].charAt(i)) {
                return strs[0].substring(0, i);
            }
        }

        return strs[0];
};

Решение на Python

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1:
            return strs[0]

        strs.sort()

        for i in range(len(strs[0])):
            if strs[0][i] != strs[-1][i]:
                return strs[0][:i]

        return strs[0]

Решение на PHP

class Solution {

    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {
        if (count($strs) == 1) {
            return $strs[0];
        }

        sort($strs);

        for ($i = 0; $i < strlen($strs[0]); $i++) {
            if ($strs[0][$i] != $strs[count($strs) - 1][$i]) {
                return substr($strs[0], 0, $i);
            }
        }

        return $strs[0];
    }
}

Решение на Csharp

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        if (strs.Length == 1) {
            return strs[0];
        }

        Array.Sort(strs);

        for (int i = 0; i < strs[0].Length; i++) {
            if (strs[0][i] != strs[strs.Length - 1][i]) {
                return strs[0].Substring(0, i);
            }
        }

        return strs[0];
    }
}