Разделение связанного предложения на отдельные слова

Question

Скажем, у меня есть следующая строка: «loveyou», мне нужно написать алгоритм, чтобы разбить его на: [«love», «you»].
У меня есть словарь со всеми возможными словами .. Я думал о том, чтобы пройти все возможные варианты и проверить, являются ли они словами:
«l oveyou», «lo veyou», «lov eyou», «люблю тебя».
Это приведет к выполнению O (n^2) времени. Существует ли более оптимизированный алгоритм?

public int splitSentence(String s) { 
    for (int i=1; i<s.length(); i++) { 
    if (isAWord(s.split(0, i) && isAWord(i, s.length()) { 
      return i; 
    } 
    } 
    return -1; 
} 

Answer 1

Я думаю, что вы можете решить вашу проблему O(mn) где m длина самого длинного слова и n длина входного потока. Мне нужно было думать об этом немного больше, но в качестве приблизительного идеи эскиз как разновидность Кнута-Морриса-Пратта:

1. Используйте prefix tree/trie для хранения списка слов.
2. Оформить список открытые позиции в Trie.
3. Перед тем, как прочитать новый символ, создайте новое открытое положение в корне дерева.
4. Для каждой открытой позиции переместите его в дереве в соответствии с символом ввода.

Когда вы достигаете листа, вы нашли слово. Поскольку вы переезжаете в худшем случае m позиций каждый раз, для каждого из входных символов n вы получаете O(mn), или действительно O(n), когда длина слов мала по сравнению с длиной входного потока.

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