algorithm - 查找对列表进行排序的替换

Question

考虑以下单词:

PINEAPPLE
BANANA
ARTICHOKE
TOMATO

目标是在不移动单词本身的情况下对其进行排序(按字典顺序)，而是使用字母替换。在此示例中，我可以将字母 P 替换为 A，将 A 替换为 P，因此:

AINEPAALE
BPNPNP
PRTICHOKE
TOMPTO

这是一个按字典顺序排列的列表。如果你切换字母，字母将在所有单词中切换。值得注意的是，您可以使用整个字母表，只使用列表中单词中的字母。

我花了相当多的时间来解决这个问题，但除了暴力破解(尝试所有字母开关组合)之外，我想不出任何其他办法，也无法想出定义列表何时可以的条件被排序。

更多例子:

ABC
ABB
ABD

可以变成

ACB
ACC
ACD

满足条件。

Answer 1

让我们暂时假设在特定情况下可能会出现该问题。此外，为简单起见，假设所有单词都是不同的(如果两个单词相同，则它们必须相邻并且可以忽略一个)。

然后问题变成了拓扑排序，虽然细节和可疑狗的答案略有不同，它遗漏了几个案例。

考虑一个包含 26 个节点的图，标记为 A通过Z .每对单词为偏序贡献一个有向边；这对应于单词不同的第一个字符。例如，使用这两个词 ABCEF和 ABRKS按顺序，第一个不同的是第三个字符，所以 sigma(C) < sigma(R) .

可以通过对该图进行拓扑排序并代入A来获得结果。对于顺序中的第一个节点，B对于第二个，等等。

请注意，这也提供了一个有用的衡量标准，说明问题何时无法解决。当两个词相同但不相邻(在“集群”中)，当一个词是另一个词的前缀但在它之后，或者当图有一个循环并且拓扑排序是不可能的时候，就会发生这种情况。

这是一个功能齐全的 Python 解决方案，包括检测问题的特定实例何时无法解决。

def topoSort(N, adj):
    stack = []
    visited = [False for _ in range(N)]
    current = [False for _ in range(N)]

    def dfs(v):
        if current[v]: return False # there's a cycle!
        if visited[v]: return True
        visited[v] = current[v] = True
        for x in adj[v]:
            if not dfs(x):
                return False
        current[v] = False
        stack.append(v)
        return True

    for i in range(N):
        if not visited[i]:
            if not dfs(i):
                return None

    return list(reversed(stack))

def solve(wordlist):
    N = 26
    adj = [set([]) for _ in range(N)] # adjacency list
    for w1, w2 in zip(wordlist[:-1], wordlist[1:]):
        idx = 0
        while idx < len(w1) and idx < len(w2):
            if w1[idx] != w2[idx]: break
            idx += 1
        else:
            # no differences found between the words
            if len(w1) > len(w2):
                return None
            continue

        c1, c2 = w1[idx], w2[idx]
        # we want c1 < c2 after the substitution
        adj[ord(c1) - ord('A')].add(ord(c2) - ord('A'))

    li = topoSort(N, adj)
    sub = {}
    for i in range(N):
        sub[chr(ord('A') + li[i])] = chr(ord('A') + i)
    return sub

def main():
    words = ['PINEAPPLE', 'BANANA', 'ARTICHOKE', 'TOMATO']
    print('Before: ' + ' '.join(words))
    sub = solve(words)
    nwords = [''.join(sub[c] for c in w) for w in words]
    print('After : ' + ' '.join(nwords))

if __name__ == '__main__':
    main()

编辑:这个解决方案的时间复杂度是可证明的最优 O(S) , 其中S是输入的长度。感谢suspicious dog为了这;原来的时间复杂度是O(N^2 L) .