Написать функцию для поиска самой длинной строки общего префикса среди массива строк.
Если общего префикса нет, вернуть пустую строку "".
Пример 1:
Входные данные: ["flower", "flow", "flight"] Выходные данные: "fl" Пример 2:
Входные данные: ["dog", "racecar", "car"] Выходные данные: "" Объяснение: У входных строк нет общего префикса. Примечание:
Все данные вводятся строчными буквами az.]
Мое текущее решение работает так:
the algo here is to take the first element in the list and compare it to the other elements
if the prefixes are different, then reduce the word from the end
flower vs flow => reduce r from flower
flowe vs flow => reduce e from flowe
flow vs flow => the same. stop
И оно работает для этого теста:
Входные данные: ["flower", "flow", "flight"]
Выходные данные: "fl"
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs) == 0:
return ""
prefix = strs[0]
for i in range(1,len(strs), 1):
while (strs[i].find(prefix) != 0): # use the function "find" to compare the next word "strs[i] and 'prefix'. If any difference, return the number of element that is different
prefix=prefix[:-i]
return prefix
Но в тестовом случае произойдет сбой [" abab "," aba "," ab c "]
Вывод:" a "
Ожидается:" ab "
Это потому, что поиск не будет работать, когда префикс длиннее других элементов и возвращает -1
>>> prefix='abab'
>>> strs='aba'
>>> strs.find(prefix)
-1
Мне интересно, есть ли какая-нибудь Java эквивалентная функция "substring" в python, которая будет работать?
Это Java решение работает с "подстрокой"
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i=1; i<strs.length; i++)
{
while (strs[i].indexOf(prefix) !=0)
{
prefix = prefix.substring(0, prefix.length()-1);
}
}
return prefix;
}
}