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) .