面试准备：优化 swapLexOrder

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

def swapLexOrder(str, pairs):
    d = {}
    d[str]=True
    while True:
        oldlen=len(d)
        for x,y in pairs:
            for s in d.keys():
                d[swp(s,x,y)]=True
        if len(d) == oldlen:
            #no more new combinations.
            return sorted(d)[-1]

def swp(str,x,y):
    x=x-1
    y=y-1
    a=str[x]
    b=str[y]
    return str[0:x]+b+str[x+1:y]+a+str[y+1:]

Answer 1

我建议的解决方案是首先尝试“链接”尽可能多的对以形成可以互换的索引集 - 例如，在您的第一个示例中，[[1, 4], [3, 4]]可以变成[[1, 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]]))

与输出：

zdsnxamwoj
dbca
zdxrabca

我还将你的参数重命名为 not use str，这已经是一个非常基本的 Python 内置函数了。请注意，我的代码可能不太 Pythonic，但我认为它足以说明算法，并且它没有遭受任何重大的性能影响。我怀疑这种方法的复杂性相当低——它通常是“智能的”，因为它不会暴力破解任何东西，并且会使用O(n log n)各种类型。第一个例子似乎是正确的。请注意，这会将每对转换为基于 0 的，因为这对于 Python 来说要容易得多。

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

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

关于 bug #1 的更多信息：

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

有关错误 #2 的更多信息：

该build_permitted_subs函数无法正常工作 - 具体来说，如果它遇到一对可以分成两个组的对，这意味着这些组也应该连接在一起，但这种情况没有发生，现在将有两个不应该分开的组。这会导致 z 重复，因为两个组都可以从 z 中提取。我用一个标志和一个追溯 for 循环草率地解决了这个问题。