在给定字符串的情况下查找单词序列的算法或步骤提示

Question

一整天都在经历这个，不知道在这里做什么，我觉得我需要在这里使用递归函数，任何提示都会很棒（采取的步骤，算法等）

给定一个词 w，w 的一个好的子序列被定义为一个词 w' 使得

• w' 中的所有字母都不同；

• w'是通过删除w中的一些字母从w中得到的。

按字典顺序返回所有好的子序列的列表，没有重复项

预期成绩：

def good_subsequences(word):

'''

>>> good_subsequences('')

['']

>>> good_subsequences('aaa')

['', 'a']

>>> good_subsequences('aaabbb')

['', 'a', 'ab', 'b']

>>> good_subsequences('aaabbc')

['', 'a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']

>>> good_subsequences('aaabbaaa')

['', 'a', 'ab', 'b', 'ba']

>>> good_subsequences('abbbcaaabccc')

['', 'a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab', 'cb']

>>> good_subsequences('abbbcaaabcccaaa')

['', 'a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac','bc', 'bca', 'c', 'ca', 'cab', 'cb', 'cba']

>>> good_subsequences('abbbcaaabcccaaabbbbbccab')

['', 'a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac','bc', 'bca', 'c', 'ca', 'cab', 'cb', 'cba']

'''

我在想的是

def good_subsequences(word):

L = ['']

current_char = ''

for i in range(0,len(word)):

    if  current_char != word[i]:

        L.append(word[i])

        current_char = word[i]

L = ''.join(L)

#call up _good_sub(L)

def _good_sub(word):

    #do a recursive function

Answer 1

与一些蛮力解决方案相比，递归生成器方法具有后续排序和很少的生产过剩：from itertools import groupbydef simple(word, without=''):    # remove adjacent duplicates and anything in 'without'    return ''.join(k for k, _ in groupby(word) if k not in without)def _gs(word):    seen = set()    s_word = simple(word)    yield ''    for i, char in enumerate(s_word):        for sub in _gs(simple(s_word[i+1:], char)):            new_sub = char + sub            if new_sub not in seen:                seen.add(new_sub)                yield new_subdef good_subsequences(word):    return sorted(_gs(word))>>> good_subsequences('')['']>>> good_subsequences('aaa')['', 'a']>>> good_subsequences('aaabbb')['', 'a', 'ab', 'b']>>> good_subsequences('aaabbc')['', 'a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']>>> good_subsequences('aaabbaaa')['', 'a', 'ab', 'b', 'ba']>>> good_subsequences('abbbcaaabccc')['', 'a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab', 'cb']

Answer 2

您可以开始执行以下操作：def good_subsequences(word):    Letter_order = [word[0]]    substrings = ['']    for i in range(1,len(word)):        if  Letter_order[-1] != word[i]:            Letter_order .append(word[i])现在，在 for 循环之后，您有一个数组，其中包含需要包含在最终子字符串数组中的所有字母顺序。在这里，您可能可以使用辅助函数根据字母在 Letter_order 数组中的顺序按顺序遍历所有可能的字母组合。

Answer 3

这只是蛮力。当您的字母表中有许多不同的字符时，请不要尝试此操作……但是如果您的字符有很多重复，它可能会执行正常。from itertools import combinations, permutationsdef in_word(strg, word):    i = 0    for char in strg:        try:            i = word.index(char, i)        except ValueError:            return False    return Truedef good_subsequences(word):    ret = ['']    alphabet = set(word)    for r in range(len(alphabet)):        for comb in combinations(alphabet, r+1):            for perm in permutations(comb, r+1):                strg = ''.join(perm)                if in_word(strg, word):                    ret.append(strg)    return ret它使用setthen 在 1、2、3、...、n 个字母组合上循环，然后在这些排列上循环，减少对唯一字母的输入。in_word然后检查该排列是否出现在您的原始单词中（按该顺序）。