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

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 groupby

def 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_sub

def 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, permutations

def in_word(strg, word):

    i = 0

    for char in strg:

        try:

            i = word.index(char, i)

        except ValueError:

            return False

    return True

def 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然后检查该排列是否出现在您的原始单词中（按该顺序）。