Question

link

Given set of words that are lexicographically sorted, return lexicographic order. E.g:

abc
acd
bcc
bed
bdc
dab

The order of letters for the given example would be

a->b->c->e->d

Solution

Just form a graph(DAG) and do a topological sort.

Start from the first pair in the dictionary. Compare two strings in this pair till first mismatch.

Eg: aad & aab, in this case create an edge d -> b.

More details is available here.

Variant, and a different solution

Another way of asking this question, is:

有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，
但是单词的顺序没有改变，比如

cat
coffee
common

--> 

dkc
dbhhzz
dbllbq

让找出的这个替换的规则（guaranteed to have a unique one)

Alternative solution is to check according to frequencies.

Code

public String lexicoOrder(String[] dict) {
	String ans = "";

	// for each pair, maintain 2 HashMap
	HashMap<Character, Integer> incount = new HashMap<Character, Integer>();
	HashMap<Character, List<Character>> connection = new HashMap<Character, List<Character>>();
	for (String str : dict) {
		for (char c : str.toCharArray()) {
			incount.put(c, 0);
			connection.put(c, new ArrayList<Character>());
		}
	}
	buildGraph(dict, incount, connection);

	// start topology sorting
	Queue<Character> temp = new LinkedList<Character>();
	for (char c : incount.keySet()) {
		if (incount.get(c) == 0) {
			temp.offer(c);
			incount.remove(c);
			// remove any node whose incount is 0
		}
	}
	while (!temp.isEmpty()) {
		char top = temp.poll();
		ans += top;
		// 'top' is next char in line. remove it and delete connections
		List<Character> inNodes = connection.get(top);
		for (char c : inNodes) {
			// remove incount for all nodes from inNodes
			incount.put(c, incount.get(c) - 1);
			if (incount.get(c) == 0) {
				incount.remove(c);
				temp.offer(c);
			}
		}
	}
	if (incount.size() == 0)
		return ans;
	else
		return "unable to find a valid char sequence.";
}

public void buildGraph(String[] dict, HashMap<Character, Integer> incount,
		HashMap<Character, List<Character>> connection) {
	// build the graph map
	// abc
	// acd
	// bcc
	// bed
	// bdc
	// dab
	for (int i = 0; i < dict.length - 1; i++) {
		// compare dict[i] and dict[i+1]
		String str1 = dict[i];
		String str2 = dict[i + 1];
		int p = 0;
		while (p < str1.length() && p < str2.length()) {
			if (str1.charAt(p) == str2.charAt(p)) {
				p++;
			} else {
				break;
			}
		}
		if (p == str1.length()) {
			// this is special case eg. "ab" & "abc"
			// this will not give up any information about lexico order
			continue;
		}
		char from = str1.charAt(p);
		char to = str2.charAt(p);
		// update incount
		incount.put(to, incount.get(to) + 1);
		// update connection
		connection.get(from).add(to);
	}
}