使用类似语法的规则减少字符串

Question

我正在尝试找到一个合适的DP算法来简化字符串.例如,我有一个字符串a b a b和一个规则列表

1. a b -> b
2. a b -> c
3. b a -> a
4. c c -> b

目的是使用这些规则获取可从给定字符串接收的所有单个字符.对于这个例子,它将是b, c.给定字符串的长度最多为200个符号.你能提示一个有效的算法吗？

规则总是如此2 -> 1.我已经知道创建一个树,root被赋予字符串,每个子节点在一次转换后是一个字符串,但我不确定它是否是最好的方法.

Answer 1

对于 DP 问题，您始终需要了解如何根据较小的子问题构建大问题的答案。simplify假设您有一个使用 length 的输入调用的函数n。有多种n-1方法可以将输入分为第一部分和最后一部分。对于每个分割，您应该simplify在第一部分和最后一部分上递归调用函数。输入长度的最终答案n是规则允许的第一部分和最后一部分答案的所有可能组合的集合。

在 Python 中，可以像这样实现：

rules = {'ab': set('bc'), 'ba': set('a'), 'cc': set('b')}
all_chars = set(c for cc in rules.values() for c in cc)

@ memoize
def simplify(s):
    if len(s) == 1:  # base case to end recursion
        return set(s)

    possible_chars = set()

    # iterate over all the possible splits of s
    for i in range(1, len(s)):
        head = s[:i]
        tail = s[i:]

        # check all possible combinations of answers of sub-problems
        for c1 in simplify(head):
            for c2 in simplify(tail):
                possible_chars.update(rules.get(c1+c2, set()))

                # speed hack
                if possible_chars == all_chars: #  won't get any bigger
                    return all_chars

    return possible_chars

快速检查：

In [53]: simplify('abab')
Out[53]: {'b', 'c'}

为了使大字符串的速度足够快（以避免指数行为），您应该使用memoize 装饰器。这是解决DP问题的关键一步，否则你只是在进行蛮力计算。通过从函数返回 ，可以获得进一步的微小加速possible_chars == set('abc')，因为此时，您已经确定可以生成所有可能的结果。

运行时间分析：对于长度为 的输入n，有 2 个长度为 的子串n-1，3 个长度为 的子串n-2，...n 个长度为 1 的子串，总共有O(n^2)子问题。由于记忆化，每个子问题最多调用该函数一次。单个子问题的最大运行时间是O(n)由于for i in range(len(s))，所以整体运行时间至多是O(n^3)。