Слово Перерыв Трудоемкость

Question

я наткнулся на проблему разрыва слово, которое идет что-то вроде этого:

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

Например, если входной является строка «applepie» и словарь содержит стандартный набор английских слов, то мы бы вернуть строку «яблочный пирог», как выход

Теперь я сам придумал квадратичное временное решение. И я наткнулся на различные other quadratic time solutions using DP.

Однако в Quora пользователь разместил linear time solution to this problem

Я не могу понять, как это выходит быть линейным. Это их ошибка в расчетах временной сложности? Какое максимальное возможное значение имеет сложную временную сложность для решения этой проблемы. Я отправляю наиболее общее решение DP здесь

String SegmentString(String input, Set<String> dict) { 
    int len = input.length(); 
    for (int i = 1; i < len; i++) { 
     String prefix = input.substring(0, i); 
     if (dict.contains(prefix)) { 
       String suffix = input.substring(i, len); 
       if (dict.contains(suffix)) { 
        return prefix + " " + suffix; 
       } 
     } 
    } 
    return null; 
} 

Answer 1

«линейный» время алгоритм, который вы linked here работает следующим образом:

Если строка sharperneedle и словарь sharp, sharper, needle,

1. It толкает sharp в строку.
2. Затем он видит, что er не в словаре, но если мы объединим его с последним добавленным словом, то sharper существует. Поэтому выскакивает последний элемент и толкает это в.

IMO выше логика не выполняется для строки eaterror и словаря eat, eater, error.

Здесь er должен выскочить из списка и нажать eater. Оставшаяся строка ror не должна распознаваться и отбрасываться.

Что касается кода, который вы опубликовали, как указано в комментариях, это работает только для двух слов с одним разделом.