给出邻接规则和未排序的数组，返回符合规则的数组

Question

假设我有一些字符数组和一组规则：

char[] chars = new int[]{ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' }; 
char[][] rules = { {'A', 'B'} , {'C', 'B'}, {'F', 'E'} }

chars中的字符是不同的，并且rules是字符对的二维数组，它们在输出中必须彼此相邻。

我想返回一个包含chars的所有元素的数组，该数组满足rules中的所有约束。如果存在多个可能的选项，则该数组应按字母顺序最早。保证至少有一种解决方案。

我将如何解决这个问题？我不太确定如何开始。

Answer 1

嗨安德鲁，我认为你擅长编程

Answer 2

由于字符是不同的，并且每个字符只能出现在输出中的两个其他字符旁边，因此每个字符最多必须以两个规则出现。如果我们将规则视为graph中的边，则它们会形成不相交的一组路径。

最早的字母顺序解决方案可以通过查找不在任何路径中或路径终点的所有字符并将它们按字母顺序插入到输出中来形成。插入路径端点后，我们必须按顺序插入该路径的其余部分，然后再继续。

[为了方便地找到具有零个或一个边的节点，并沿着路径进行迭代，我们将从将edge list data structure转换为adjacency list data structure开始。

import java.util.*;

public class Solution {
    public static char[] solve(char[] letters, char[][] rules) {
        // convert to adjacency list
        Map<Character, List<Character>> neighbours = new HashMap<>();
        for(char[] edge : rules) {
            char a = edge[0], b = edge[1];
            neighbours.computeIfAbsent(a, ArrayList::new).add(b);
            neighbours.computeIfAbsent(b, ArrayList::new).add(a);
        }

        // find nodes with 0 or 1 edges, in order
        List<Character> endpoints = new ArrayList<>();
        for(char a : letters) {
            if(!neighbours.containsKey(a) || neighbours.get(a).size() <= 1) {
                endpoints.add(a);
            }
        }
        Collections.sort(endpoints);

        // build output
        char[] out = new char[letters.length];
        Set<Character> used = new HashSet<>();
        int i = 0;
        for(char a : endpoints) {
            if(used.contains(a)) { continue; }
            out[i++] = a;
            used.add(a);
            // if it's a path, iterate along path
            while(neighbours.containsKey(a) && !neighbours.get(a).isEmpty()) {
                char b = neighbours.get(a).get(0);
                out[i++] = b;
                used.add(b);
                // remove previous neighbour so next one guaranteed at index 0
                neighbours.get(b).remove((Character) a); // don't convert to int
                a = b;
            }
        }
        return out;
    }
}

示例：

>>> Solution.solve(
...     new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' },
...     new char[][] { {'A', 'B'} , {'D', 'B'}, {'G', 'E'}, {'H', 'A'} }
... )
... 
char[8] { 'C', 'D', 'B', 'A', 'H', 'E', 'G', 'F' }