Поиск самого длинного общего префикса в строках

Легкая

string , easy

15 September 2023

Описание задачи #

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

Входные данные: массив строк.

Выходные данные: строка, являющаяся самым длинным общим префиксом для всех строк массива.

Ограничения #

В массиве строк может быть от 1 до 200 элементов
Длина каждой строки от 0 до 200 символов
Каждая строка состоит только из строчных английских букв

Примеры #

Входные данные: ["flower","flow","flight"]

Ответ: "fl"
Входные данные: ["dog","racecar","car"]

Ответ: ""

Решение #

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

Итоговый алгоритм:

Выбираем одну из строк массива по которой будем итерироваться. Для удобства можно выбрать первую.
Итерируемся по выбранной строке посимвольно. Для каждого символа запускаем новый цикл, в котором проверяем, что во всех строках на соответствующем индексе стоит один и тот же символ.
Если символ по индексу во всех строках одинаковый, то добавляем его к строке-результату
Прекращаем итерации и возвращаем префикс в виде строки как только встречается первый несовпадающий символ или если превышается длина любой из строк.

package main

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

	prefix := ""
	firstStr := strs[0]

	for idx, char := range firstStr {
		for _, str := range strs {
			if idx >= len(str) || str[idx] != firstStr[idx] {
				return prefix
			}
		}

		prefix += string(char)
	}

	return prefix
}

export const longestCommonPrefix = (strs: string[]): string => {
	if (strs.length == 0) {
		return ""
	}

	let prefix = ''
	const firstStr = strs[0]

	for (let i = 0; i < firstStr.length; i++) {
		const char = firstStr[i]

		for (let j = 0; j < strs.length; j++) {
			const str = strs[j]
			if (i >= str.length || str[i] != firstStr[i]) {
				return prefix
			}
		}

		prefix += char
	}

	return prefix
}

Оценка сложности #

По времени

Сложность O(m * n), где n — количество строк в массиве, m — длина самой короткой строки. Мы итерируемся по строке и сравниваем соответствующие текущему индексу символы в каждой из строк.

По памяти

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

Оригинал задачи на Leetcode

Algorithmics