Недавно я наткнулся на следующий вопрос интервью:
Учитывая входную строку и словарь слов, реализуйте метод, который разбивает входную строку на строку словарных слов, разделенную пробелами, которую может использовать поисковая система для "Вы имели в виду?". Например, ввод "applepie" должен давать результат "яблочного пирога".
Я не могу найти оптимального решения в отношении сложности. Есть ли у кого-нибудь предложения по эффективному использованию?
Похоже, что вопрос - это именно моя проблема с интервью, вплоть до примера, который я использовал в сообщении на канале Noisy Channel. Рад, что вам понравилось решение. Я уверен, что вы не можете победить решение динамического программирования /memoization O (n ^ 2), которое я описываю для наихудших результатов.
На практике вы можете сделать лучше, если ваш словарь и ввод не являются патологическими. Например, если вы можете идентифицировать в линейном времени подстроки входной строки в словаре (например, с помощью trie), и если число таких подстрок будет постоянным, тогда общее время будет линейным. Конечно, много предположений, но реальные данные часто намного приятнее, чем патологический худший случай.
Существуют также забавные варианты проблемы, чтобы сделать ее более сложной, например перечисление всех допустимых сегментов, выводящую лучшую сегментацию на основе некоторого определения наилучшего, обработку словаря, слишком большого для размещения в памяти, и обработку неточных сегментов (например, исправление орфографических ошибок). Не стесняйтесь комментировать мой блог или иным образом связываться со мной, чтобы следить за ней.
Эта ссылка описывает эту проблему как идеальный вопрос для интервью и предлагает несколько способов ее решения. По существу это включает рекурсивный откат. На этом уровне он создавал бы сложность O (2 ^ n). Эффективное решение с использованием memoization может привести эту проблему к O (n ^ 2).
Используя python, мы можем написать две функции, первая из которых segment возвращает первую сегментацию части непрерывного текста в слова, заданные в словаре или None, если такая сегментация не найдена. Другая функция segment_all возвращает список всех найденных сегментов. Хуже всего сложность случая O (n ** 2), где n - длина входной строки в символах.
Решение, представленное здесь, может быть расширено для включения исправлений орфографии и анализа bigram для определения наиболее вероятной сегментации.
def memo(func):
'''
Applies simple memoization to a function
'''
cache = {}
def closure(*args):
if args in cache:
v = cache[args]
else:
v = func(*args)
cache[args] = v
return v
return closure
def segment(text, words):
'''
Return the first match that is the segmentation of 'text' into words
'''
@memo
def _segment(text):
if text in words: return text
for i in xrange(1, len(text)):
prefix, suffix = text[:i], text[i:]
segmented_suffix = _segment(suffix)
if prefix in words and segmented_suffix:
return '%s %s' % (prefix, segmented_suffix)
return None
return _segment(text)
def segment_all(text, words):
'''
Return a full list of matches that are the segmentation of 'text' into words
'''
@memo
def _segment(text):
matches = []
if text in words:
matches.append(text)
for i in xrange(1, len(text)):
prefix, suffix = text[:i], text[i:]
segmented_suffix_matches = _segment(suffix)
if prefix in words and len(segmented_suffix_matches):
for match in segmented_suffix_matches:
matches.append('%s %s' % (prefix, match))
return matches
return _segment(text)
if __name__ == "__main__":
string = 'cargocultscience'
words = set('car cargo go cult science'.split())
print segment(string, words)
# >>> car go cult science
print segment_all(string, words)
# >>> ['car go cult science', 'cargo cult science']
Один из вариантов - сохранить все действующие английские слова в trie. После того, как вы это сделаете, вы можете начать движение по три от корня вниз, следуя буквам в строке. Всякий раз, когда вы найдете node, который помечен как слово, у вас есть два варианта:
Вы можете утверждать, что вы нашли совпадение после того, как вы ввели слово в набор слов, которые являются законными, и не осталось оставшихся символов. Поскольку на каждой букве у вас есть один принудительный вариант (либо вы строите слово, которое недопустимо, и должно прекратить -или- вы можете продолжать расширять слово), либо два варианта (разделение или продолжение), вы можете реализовать эту функцию используя исчерпывающую рекурсию:
PartitionWords(lettersLeft, wordSoFar, wordBreaks, trieNode):
// If you walked off the trie, this path fails.
if trieNode is null, return.
// If this trie node is a word, consider what happens if you split
// the word here.
if trieNode.isWord:
// If there is no input left, you're done and have a partition.
if lettersLeft is empty, output wordBreaks + wordSoFar and return
// Otherwise, try splitting here.
PartitinWords(lettersLeft, "", wordBreaks + wordSoFar, trie root)
// Otherwise, consume the next letter and continue:
PartitionWords(lettersLeft.substring(1), wordSoFar + lettersLeft[0],
wordBreaks, trieNode.child[lettersLeft[0])
В патологически худшем случае это будет перечислять все разделы строки, которые могут экспоненциально длиться. Однако это происходит только в том случае, если вы можете разбить строку на огромное количество способов, которые начинаются с действительных английских слов, и вряд ли это произойдет на практике. Если строка содержит много разделов, мы могли бы потратить много времени на их поиск. Например, рассмотрим строку "dotheredo". Мы можем разделить это множество способов:
do the redo
do the red o
doth ere do
dot here do
dot he red o
dot he redo
Чтобы этого избежать, вы можете установить ограничение на количество ответов, которые вы сообщаете, возможно, два или три.
Так как мы отрезали рекурсию, когда мы выходим из trie, если мы когда-нибудь попробуем раскол, который не оставит оставшуюся часть строки действительной, мы обнаружим это довольно быстро.
Надеюсь, это поможет!
import java.util. *;
class Position {
int indexTest,no;
Position(int indexTest,int no)
{
this.indexTest=indexTest;
this.no=no;
} } class RandomWordCombo {
static boolean isCombo(String[] dict,String test)
{
HashMap<String,ArrayList<String>> dic=new HashMap<String,ArrayList<String>>();
Stack<Position> pos=new Stack<Position>();
for(String each:dict)
{
if(dic.containsKey(""+each.charAt(0)))
{
//System.out.println("=========it is here");
ArrayList<String> temp=dic.get(""+each.charAt(0));
temp.add(each);
dic.put(""+each.charAt(0),temp);
}
else
{
ArrayList<String> temp=new ArrayList<String>();
temp.add(each);
dic.put(""+each.charAt(0),temp);
}
}
Iterator it = dic.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pair = (Map.Entry)it.next();
System.out.println("key: "+pair.getKey());
for(String str:(ArrayList<String>)pair.getValue())
{
System.out.print(str);
}
}
pos.push(new Position(0,0));
while(!pos.isEmpty())
{
Position position=pos.pop();
System.out.println("position index: "+position.indexTest+" no: "+position.no);
if(dic.containsKey(""+test.charAt(position.indexTest)))
{
ArrayList<String> strings=dic.get(""+test.charAt(position.indexTest));
if(strings.size()>1&&position.no<strings.size()-1)
pos.push(new Position(position.indexTest,position.no+1));
String str=strings.get(position.no);
if(position.indexTest+str.length()==test.length())
return true;
pos.push(new Position(position.indexTest+str.length(),0));
}
}
return false;
}
public static void main(String[] st)
{
String[] dic={"world","hello","super","hell"};
System.out.println("is 'hellworld' a combo: "+isCombo(dic,"superman"));
} }
У меня была аналогичная проблема. Это решение дает true или false, если заданная строка представляет собой комбинацию словарных слов. Его можно легко преобразовать, чтобы получить строку, разделенную пространством. Его средняя сложность - O (n), где n: нет словарных слов в данной строке.