面试准备：优化swapLexOrd

Question

面试散列图问题上的代码打架，需要帮助优化我的暴力解决方案。问题是：

给定一个字符串str和一对数组，该数组指示可以交换字符串中的哪些索引，则返回执行所允许的交换所得到的字典上最大的字符串。可以多次交换索引。在

示例

For str = "abdc" and pairs = [[1, 4], [3, 4]], the output should be
swapLexOrder(str, pairs) = "dbca".

通过交换给定的索引，可以得到字符串：“cbda”、“cbad”、“dbac”、“dbca”。这个列表中字典式最大的字符串是“dbca”。在

我当前的解决方案

通过不断增加所有的可能性，直到没有新的解决方案。这对swapLexOrder('dznsxamwoj',[[1,2],[3,4],[6,5],[8,10]])来说太慢了，无法在我的计算机上完成。有什么优化建议吗？一个更容易通过的测试用例是swapLexOrder('abdc,[[1,4],[3,4]])= dbca

^{pr2}$

Answer 1

这个也许效果更好。在

def swapLexOrder(str_, pairs):
n = len(str_)
str_ = list(str_)

corr = [set() for _ in range(n)]
nodes = set()
for a, b in pairs:
    corr[a-1].add(b-1)
    corr[b-1].add(a-1)
    nodes.add(a-1)
    nodes.add(b-1)

while nodes:
    active = {nodes.pop()}
    group = set()
    while active:
        group |= active
        nodes -= active
        active = {y for x in active for y in corr[x] if y in nodes}

    chars = iter(sorted((str_[i] for i in group), reverse=True))
    for i in sorted(group):
        str_[i] = next(chars)

return "".join(str_)

Answer 2

我建议的解决方案是首先尝试“链接”尽可能多的对，以形成可以互换的索引集-例如在第一个示例中，[[1, 4], [3, 4]]可以变成{}。然后，这些索引子集中的每一个子集都可以按字典顺序排序以形成输出。实施过程如下：

def build_permitted_subs(pairs):
    perm = []

    for a, b in pairs:
        merged = False
        for ind, sub_perm in enumerate(perm):
            if a in sub_perm or b in sub_perm:
                sub_perm.add(a)
                sub_perm.add(b)
                merged = True
                break

        else:
            perm.append(set([a, b]))

        if merged:
            for merge_perm_ind in reversed(range(ind + 1, len(perm))):
                if perm[merge_perm_ind] & sub_perm:
                    sub_perm.update(perm[merge_perm_ind])
                    perm.pop(merge_perm_ind)

    return list(map(sorted, perm))

def swap_lex_order(swap_str, _pairs):

    pairs = [[a - 1, b - 1] for a, b in _pairs]
    out = list(swap_str)

    perm = build_permitted_subs(pairs)

    for sub_perm in perm:
        sorted_subset = sorted(sub_perm, key=lambda ind: swap_str[ind], reverse=True)

        for sort, targ in zip(sorted_subset, sub_perm):
            out[targ] = swap_str[sort]

    return "".join(out)

print(swap_lex_order("dznsxamwoj", [[1, 2], [3, 4], [6, 5], [8, 10]]))
print(swap_lex_order("abdc", [[1, 4], [3, 4]]))
print(swap_lex_order("acxrabdz",[[1,3], [6,8], [3,8], [2,7]]))

带输出：

^{pr2}$

我还将参数重命名为不使用str，这已经是一个非常基本的Python内置。请注意，我的代码可能不是尽可能的Pythonic，但是我认为它可以很好地演示算法，而且它不会受到任何性能的严重影响。我怀疑这种方法的复杂度很低-它通常是“智能”的，因为它不会对任何东西进行暴力攻击，并且使用O(n log n)排序。第一个例子似乎是正确的。请注意，这会将每个对转换为基于0的，因为这对于Python来说更容易。在

这有点依赖于能够从相邻的排列（交换对）中形成任何排列（对链接的对进行排序）。这可能不是完全直观的，但它可能有助于您认识到，您可以仅使用列表中相邻的交换来有效地执行插入（通过在要执行的方向上不断交换元素）。使用相邻交换排列列表的一个例子是bubblesort，您可能意识到，如果任何置换都可以进行bubblesort，那意味着所有的置换都可以通过bubblesort来实现。在

如果您有任何问题，或者任何东西不起作用，请告诉我，我将开始详细说明/调试。（截至格林尼治标准时间19:28，我已经注意到一个bug并将其编辑掉：）。Bug#2（测试用例3有重复的z）也应该被修复。在

关于bug#1的更多信息：

我没有对build_permitted_subs返回的索引进行排序，因此它无法参照swap_str对它们进行正确排序。在

有关bug#2的更多信息：

build_permitted_subs函数不能正常工作——特别是，如果它遇到一对可以分成两个组的对，这意味着这些组也应该结合在一起，这就不会发生，现在会有两个组不应该分开。这会导致z重复，因为两个组都可以从z轴绘制。我已经用一个标志和一个追溯for循环草率地修复了这个问题。在