Вопрос — Сложность — Легко
Напишите функцию для поиска самой длинной строки с общим префиксом среди массива строк.
Если общего префикса нет, верните пустую строку «».
Пример 1:
Входные данные: Strings = [«flower», «flow», «flight»].
Выходные данные: «fl»
Пример 2:
Вход: Строки = [«dog», «raceCar», «car»]
Выходные данные: «»
Объяснение: Среди входных строк нет общего префикса.
Ограничения:
1 <= Strings.length <= 200
0 <= Strings[i].length <= 200
Strings[i] состоит только из строчных английских букв.
Теоретическое описание
- Итерация строки по очереди от S1 до SN.
- Начните сравнивать 0-й индекс, 1-й индекс … 1-й индекс одновременно для каждой строки.
- В случае, если ни один из символов ith-индекса не совпадает, завершите алгоритм и верните LPS(1,i).
- Иначе, продолжайте и после сканирования N строк, можно получить LCP(S1…SN).
Напоминание:-
Оба решения идеальны, но первое решение требует слишком много времени на выполнение, поэтому в итоге выдается ошибка Time Exceed Error.
НО
Второе решение работает как шарм.
class A {
// Not Working - Horizontal Scan
String longestCommonPrefix(List<String> strs) {
// Checking if the list is empty
if (strs.length == 0 || strs.isEmpty || strs.length == '') return "";
// Storing the first index value in a variable
String prefix = strs[0];
// looping the whole length of list inside the list
// like how many strings are available
for (var i = 0; i < strs.length; i++) {
// storing the whole list in a variable
String c = strs[i];
if (c.length == 0 || prefix == "") return "";
// setting the first index starting point in subString 0 is first string
// AND entire length of the remaining list
prefix = prefix.substring(0, min(prefix.length, c.length));
for (var j = 0; j < c.length && j < prefix.length; j++) {
if (c[j] != prefix[j]) {
prefix = prefix.substring(0, j);
break;
}
}
}
return prefix;
}
}
class B {
// Vertical scan -Working
String longestCommonPrefix(List<String> strs) {
if (strs.length == 0 || strs.isEmpty || strs.length == '') return "";
// looping through the length of list
for (int i = 0; i < strs[0].length; i++) {
// storing the value of first index and the other strings
String c = strs[0][i];
// looping again the entire length without index
for (int j = 1; j < strs.length; j++) {
// if the the length is same as the length of the above loop
//OR indexes of the list is not same as above
if (i == strs[j].length || strs[j][i] != c)
// returning the first index and subString starting
// from first index and the remaining index
return strs[0].substring(0, i);
}
}
return strs[0];
}
}
Время выполнения: 426 мс, быстрее, чем 100,00% онлайн-заявок Dart для Longest Common Prefix.
Использование памяти: 141,9 МБ, меньше, чем в 100,00% случаев использования префикса Longest Common в Dart.