269 Alien Dictionary
Problem:
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example 1: Given the following words in dictionary,
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
The correct order is: "wertf".
Example 2: Given the following words in dictionary,
[
"z",
"x"
]
The correct order is: "zx".
Example 3: Given the following words in dictionary,
[
"z",
"x",
"z"
]
The order is invalid, so return "".
Note:
- You may assume all letters are in lowercase.
- You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
- If the order is invalid, return an empty string.
- There may be multiple valid order of letters, return any one of them is fine.
Solutions:
public class Solution {
public String alienOrder(String[] words) {
HashSet<Character> cand = new HashSet<Character>();
int n = 0;
HashMap<Character, HashSet<Character>> less = new HashMap<Character, HashSet<Character>>();
HashMap<Character, HashSet<Character>> greater = new HashMap<Character, HashSet<Character>>();
for (int i = 0; i < words.length; i ++) {
String word = words[i];
for (int j = 0; j < word.length(); j ++) {
cand.add(word.charAt(j));
}
if (i > 0) {
String s1 = words[i - 1];
String s2 = words[i];
int i1 = 0;
int i2 = 0;
while (i1 < s1.length() && i2 < s2.length()) {
char c1 = s1.charAt(i1);
char c2 = s2.charAt(i2);
if (c1 != c2) {
update(c1, c2, less, greater);
break;
}
i1 ++;
i2 ++;
}
}
}
String result = "";
n = cand.size();
while (true) {
Character c = min(cand, less, greater);
if (c == null) {
break;
}
result += c;
cand.remove(c);
}
if (result.length() != n) {
return "";
}
return result;
}
private Character min(HashSet<Character> cand, HashMap<Character, HashSet<Character>> less, HashMap<Character, HashSet<Character>> greater) {
for (Character c:cand) {
if (!greater.containsKey(c)) {
if (less.containsKey(c)) {
for (Character cc:less.get(c)) {
greater.get(cc).remove(c);
if (greater.get(cc).isEmpty()) {
greater.remove(cc);
}
}
less.remove(c);
}
return c;
}
}
return null;
}
private void update(char c1, char c2, HashMap<Character, HashSet<Character>> less, HashMap<Character, HashSet<Character>> greater) {
if (!less.containsKey(c1)) {
less.put(c1, new HashSet<Character>());
}
less.get(c1).add(c2);
if (!greater.containsKey(c2)) {
greater.put(c2, new HashSet<Character>());
}
greater.get(c2).add(c1);
}
}
public class Solution {
public String alienOrder(String[] words) {
HashSet<Character> cand = new HashSet<Character>();
HashMap<Character, HashSet<Character>> less = new HashMap<Character, HashSet<Character>>();
int[] inDegree = new int[26];
for (int i = 0; i < words.length; i ++) {
String word = words[i];
for (int j = 0; j < word.length(); j ++) {
cand.add(word.charAt(j));
}
if (i > 0) {
String s1 = words[i - 1];
String s2 = words[i];
int i1 = 0;
int i2 = 0;
while (i1 < s1.length() && i2 < s2.length()) {
char c1 = s1.charAt(i1);
char c2 = s2.charAt(i2);
if (c1 != c2) {
update(c1, c2, less, inDegree);
break;
}
i1 ++;
i2 ++;
}
}
}
Queue<Character> q = new LinkedList<Character>();
for (int i = 0; i < inDegree.length; i ++) {
char c = (char)(i + 'a');
if (inDegree[i] == 0 && cand.contains(c)) {
q.add(c);
}
}
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
Character dest = q.poll();
sb.append(dest);
if (less.containsKey(dest)) {
for (Character c:less.get(dest)) {
inDegree[c - 'a'] --;
if (inDegree[c - 'a'] == 0) {
q.add(c);
}
}
}
}
if (sb.length() != cand.size()) {
return "";
}
return sb.toString();
}
private void update(char c1, char c2, HashMap<Character, HashSet<Character>> less, int[] inDegree) {
if (!less.containsKey(c1)) {
less.put(c1, new HashSet<Character>());
}
if (!less.get(c1).contains(c2)) {
less.get(c1).add(c2);
inDegree[c2 - 'a'] ++;
}
}
}