Я прочитал эту статью Retiring a Great Interview Problem, автор придумал проблему work break
и дал три решения. Эффективный использует алгоритм memoization
, и автор сказал, что его наихудшая временная сложность составляет O(n^2)
с the key insight is that SegmentString is only called on suffixes of the original input string, and that there are only O(n) suffixes
.Временная сложность алгоритма запоминания
Однако мне трудно понять, почему это O(n^2)
. Может кто-нибудь, пожалуйста, дайте мне подсказку или доказательство?
Work Break Problem:
Given an input string and a dictionary of words,
segment the input string into a space-separated
sequence of dictionary words if possible. For
example, if the input string is "applepie" and
dictionary contains a standard set of English words,
then we would return the string "apple pie" as output.
мемоизации алгоритм из Retiring a Great Interview Problem
Map<String, String> memoized;
String SegmentString(String input, Set<String> dict) {
if (dict.contains(input))
return input;
if (memoized.containsKey(input) {
return memoized.get(input);
}
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);
String segSuffix = SegmentString(suffix, dict);
if (segSuffix != null) {
return prefix + " " + segSuffix;
}
}
}
memoized.put(input, null);
return null;
}
Решение не является оптимальным, оно только обновляет memoized карту, когда результат ввода строки является нулевым, должен обновляться во всех случаях! –
Это правильно. Обратите внимание, что 'segSuffix' называется только recusively, если' prefix' находится в слове в 'dict'. Если этот рекурсивный вызов возвращает non-'null', вызывающий абонент также сразу же возвращает его в стек. Другими словами, как только вызов 'segSuffix' возвращает значение, отличное от' null', алгоритм никогда не вызывает 'segSuffix' снова, поэтому значение non-' null' не нужно запоминать. – Alp
@Alp Ницца, спасибо. В этом случае достаточно только массива логических значений, поскольку мы всегда можем ссылаться на суффикс как на его индекс во всей строке ввода. –