从列表中查找适合给定单词的所有单词排列

Question

如果我有“有时”这个词并且我有单词列表

有效单词：

["some","time","rome","sometime","so","me"]

我要输出结果

结果 =

[["so","me","time"],["some","time"],["sometime"]]

我知道我应该使用 DFS，但我不知道如何编码。我与排列作斗争。有人可以帮助我吗？

这就是我目前所拥有的

def letterCombinations(word, valid_words):
    result = []
    def dfs(string_path, i, valid_word_set, curr_string):
      if i == len(word):
        return

      if string_path[:i] in valid_word_set:
        curr_string.append(string_path[:i])
        dfs(string_path[i:], i+1, valid_word_set, curr_string)
      else:
        dfs(string_path, i+1, valid_word_set, curr_string)
        
    for i in range(0, len(word)):
        if word[:i] in valid_words:
          curr_string = [word[:i]]
          dfs(word[i:], i, valid_words, curr_string)
          result.append(curr_string)
    
    return result

Answer 1

这应该对你有用。 它使用递归来循环遍历所有组合并将找到的单词存储在集合中，因此您本质上是在缓存

def letter_combos(word: str, word_dict: list[str]) -> list[list[str]]:
    def dfs(word: str, valid_word_set: set[str], start: int, memo: dict[int, list[list[str]]]) -> list[list[str]]:
        if start in memo:
            return memo[start]
        res: list[list[str]] = []
        if start == len(word):
            res.append([])
        for end in range(start + 1, len(word) + 1):
            if word[start:end] in word_dict:
                list_of_words = dfs(word, valid_word_set, end, memo)
                for lst in list_of_words:
                    res.append([word[start:end]] + lst)
        memo[start] = res
        return res
    return dfs(word, set(word_dict), 0, {})

word = "sometime"
valid_words = ["some", "time", "rome", "sometime", "so", "me"]

print(letter_combos(word, valid_words))

>>> [['so', 'me', 'time'], ['some', 'time'], ['sometime']]

您还可以使用 functools lru_cache 来稍微整理一下

from functools import lru_cache

def letter_combos(word: str, valid_words: list[str]) -> list[list[str]]:
    @lru_cache(maxsize=None) 
    def dfs(start: int) -> list[list[str]]:
        if start == len(word):  
            return [[]]
        result: list[list[str]] = []
        for end in range(start + 1, len(word) + 1):
            if word[start:end] in valid_word_set:
                for lst in dfs(end):
                    result.append([word[start:end]] + lst)
        return result

    valid_word_set = set(valid_words)
    return dfs(0)

word = "sometime"
valid_words = ["some", "time", "rome", "sometime", "so", "me"]
print(letter_combos(word, valid_words))

Answer 2

基于

itertools.permutations

和生成器函数的替代解决方案：

from itertools import permutations

def match_perms(word, valid_words):
    words = valid_words[:]
    if word in words:   # if the whole word is found in words list
        yield (word,)
        words.remove(word)  # excude it from permutations

    for i in range(2, len(words)):
        for p in permutations(words, i):
            if ''.join(p) == word:
                yield p

print(list(match_perms(word, valid_words)))

---

[('sometime',), ('some', 'time'), ('so', 'me', 'time')]

Answer 3

递归方法，还使用

Counter

:

考虑潜在的重复单词

from collections import Counter

word = 'sometime'
valid_words = ['some', 'time', 'rome', 'sometime', 'so', 'me']

def find_comb(word, valid_words, stem=None):
    if stem is None:
        stem = []
    if not isinstance(valid_words, Counter):
        valid_words = Counter(valid_words)
    if word in valid_words:
        yield stem + [word]
    for w in valid_words:
        if word.startswith(w):
            yield from find_comb(word[len(w):],
                                 valid_words-Counter({w: 1}),
                                 stem=stem+[w])  
    
out = list(find_comb(word, valid_words))

输出：

[['sometime'], ['some', 'time'], ['so', 'me', 'time']]

其他例子：

list(find_comb('banana', ['banana', 'ba', 'na', 'na', 'nana']))
# [['banana'], ['ba', 'nana'], ['ba', 'na', 'na']]

list(find_comb('banana', ['banana', 'ba', 'na', 'nana']))
# [['banana'], ['ba', 'nana']]

Answer 4

def letterCombinations(word, valid_words):
      result = []

    
    def dfs(string_path, valid_word_set, curr_string):
        if not string_path:
            result.append(curr_string[:])  # Append a copy of the current string to the result list
            return
        
        for i in range(1, len(string_path) + 1):
            if string_path[:i] in valid_word_set:
                curr_string.append(string_path[:i])
                dfs(string_path[i:], valid_word_set, curr_string)
                curr_string.pop()  # Backtrack by removing the last element from the current string
    
       valid_word_set = set(valid_words)
       dfs(word, valid_word_set, [])
       return result

    word = "sometime"
    valid_words = ["some", "time", "rome", "sometime", "so", "me"]
    result = letterCombinations(word, valid_words) 
    print(result)

我认为这对你有用，如果不起作用请告诉我