Оптимизация кода с потенциальным полиномиальным временем выполнения Big O - PullRequest
Новая
       12

Оптимизация кода с потенциальным полиномиальным временем выполнения Big O

0 голосов
/ 23 апреля 2019

В одном из моих интервью мне задали вопрос, чтобы определить, является ли данная строка допустимой английской фразой. Рассматриваемая строка представляет собой набор буквенно-цифровых символов без разделителей, включая пробелы. Предполагалось, что где-то был «словарь», в котором содержались все допустимые слова, и его можно было использовать как ссылку для определения, является ли слово действительным или нет. Этот «словарь» может быть реализован с использованием любого подходящего механизма / структуры данных.

Мое решение было сделано с использованием Python и включало рекурсию. Вот что я предложил: 

def isphrase(string, words):
"""
Determine if a given string (containing no spaces or delimiters) is a 
valid English phrase
:param string: String to be checked
:param words: Collection of English words as an iterable or in a file
:return:  True, if it is a phrase
         False, otherwise
"""

if len(string) == 0:
    return True

if string in words:
    return True

for i in range(len(string)):
    if string[:i+1] in words and isphrase(string[i+1:], words):
        return True

return False


if __name__ == '__main__':
    words = {"i", "am", "here", "there", "you", "were"}
    print(isphrase("thereyou", words))

Решение было принято в качестве жизнеспособного решения, но, решая сложность времени, это выявляется в виде O (n!) В худшем случае. Есть ли способ сделать это ближе к O (nlogn) или что-то вроде этого? Должен ли я принять философию «разделяй и властвуй» вместо этого подхода?

P.S .: Я использовал набор для хранения набора слов. Пожалуйста, не стесняйтесь предоставлять свои предложения / комментарии по этому вопросу.

1 Ответ

0 голосов
/ 23 апреля 2019

Вот решение для динамического программирования: 

def isphrase(s, word_dict):
    size = len(s)

    if size == 0:
        return False

    dp = [False]*(size+1)
    dp[0] = True
    for i in range(size):
        if dp[i]:
            for j in range(i, size):
                if s[i:j+1] in word_dict:
                    dp[j+1] = True
    return dp[j+1]

if __name__ == '__main__':
    words = {"i", "am", "here", "there", "you", "were"}
    print(isphrase("thereyou", words))

Вы можете хранить подслов в списке, чтобы вы не могли постоянно пересчитывать их. Более быстрое решение - использовать подход динамического программирования «сверху вниз» (оставленный читателю в качестве упражнения), или вместо этого можно использовать три.

...