1

对于给定的输入字符串input = "abbbbdeeefffddddb"，我想将其解析为

result = ['a', 'b', 'bb', 'bd', 'd', 'e', 'ee', 'f', 'ff', 'dd', 'db']

此解析背后的逻辑如下。如果第一次遇到子字符串，则将其解析掉。在每个后续出现的子字符串中，它与以下字母连接，然后被解析掉。

为了显示：

  1. 我们以前见过“a”（位置 0）吗？没有解析它。
  2. 我们以前见过“b”（位置 1）吗？没有解析它。
  3. 我们以前见过“b”（位置 2）吗？是的; 与以下字母合并
  4. 我们以前见过“bb”（位置 2 和 3）吗？没有解析它。
  5. 我们以前见过“b”（位置 4）吗？YES 与以下字母合并
  6. 我们以前见过“bd”（位置 4 和 5）吗？不解析它...

这种情况一直持续到最后。

我尝试使用以下代码来实现这一点：

input = "abbbbdeeefffddddb"

comparator = []

def parse(string):
    for pointer in range(len(string)-1):
        if string[pointer] not in comparator:
            comparator.append(string[pointer])

        else:
            substring = string[pointer] + string[pointer+1]
            comparator.append(substring)

        print comparator 

parse(input)

这是结果：['a', 'b', 'bb', 'bb', 'bd', 'd', 'e', 'ee', 'ef', 'f', 'ff', 'fd', 'dd', 'dd', 'dd', 'db']

这是错误的。我在这里遗漏了一个关键部分，但我不知道如何实现它，也许它需要一些递归函数，或者我应该使用break或continue某处。

不要只为这个给定的输入提供解决方案。这里给出的输入只是为了举例。解决方案必须是通用的，以适用于不同的输入。

这是原始算法，第 6 页：论文

4

3 回答 3

2

这是关于你想要的吗？

$ cat single-seen-double
#!/usr/bin/python3

def single_seen_double(string):
    length = len(string)
    index = 0
    seen = set()
    while index < length:
        if string[index] in seen and index < length - 1:
            yield string[index:index+2]
            index += 2
        else:
            seen.add(string[index])
            yield string[index]
            index += 1

def main():
    print(list(single_seen_double("abbbbdeeefffddddb")))

main()

zareason-dstromberg:~/src/outside-questions/single-seen-double x86_64-pc-linux-gnu 5871 - above cmd done 2013 Tue Nov 05 01:48 PM

$ ./single-seen-double
['a', 'b', 'bb', 'bd', 'e', 'ee', 'f', 'ff', 'd', 'dd', 'db']

它没有给出你的样本输出，但我想知道这是否不是你真正想要的。如果这不是您所需要的，您能否更具体地说明您需要遵循的规则？

于 2013-11-05T21:51:20.103 回答
2

您似乎忘记了从二元组中跳过已解析的字母：

def parse(string):
    pointer = 0
    while pointer < len(string):
        if string[pointer] not in comparator:
            comparator.append(string[pointer])
        else:
            substring = string[pointer] + string[pointer+1]
            comparator.append(substring)
            pointer += 1
        pointer += 1
    print comparator
['a', 'b', 'bb', 'bd', 'e', 'ee', 'f', 'ff', 'd', 'dd', 'db']

或稍微改写

def parse(string):
    result = set()
    letters = iter(string)
    for letter in letters:
        if letter not in result:
            result.add(letter)
        else:
            substring = letter + letters.next()
            result.add(substring)
    return list(result)
# same set, different order
['a', 'bd', 'b', 'e', 'd', 'bb', 'f', 'ee', 'dd', 'db', 'ff']
于 2013-11-05T21:36:07.203 回答
0

使用 set 有什么问题？

set(comparator)

如果订单不重要。

于 2013-11-05T21:40:55.120 回答