Compare each consecutive pair of words to extract ordering constraints between individual characters.

Alien Dictionary

hard

Acceptance: 37%

GraphsTopological Sort

An unknown language uses familiar English letters but in a different alphabetical order. Given a list of words sorted according to this unknown ordering, deduce the order of the letters. If the given ordering is contradictory, return an empty string. If multiple valid orderings exist, return any one of them.

Examples

Example 1:

Input:words = ["ba","bc","ac","cab"]

Output:"bac"

Explanation: From ba < bc: a < c. From bc < ac: b < a. From ac < cab: a < c (already known). Order: b, a, c.

Example 2:

Input:words = ["x","y","x"]

Output:""

Explanation: x < y and y < x is contradictory.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Alien Dictionary

Examples

Hints

Related Problems