Alien Dictionary

https://leetcode.com/problems/alien-dictionary/

This is a cool problem, but I made it all by myself! Cheers! It took me 4 hours to figure it out, but definitely worth of it.

  • This problem is about topological sort:
    • find all relative lexicographical order between the letters
    • then build a topological order out of it
    • check if all indegree  becomes zero in the end, if not, that means there’s a cycle in the graph, then return an empty string

public String alienOrder(String[] words) {
// we collect all relative order between the two letters from the given list of words and
// store them as this: "ab" means 'a' is preceding 'b'
Set<String> orders = new HashSet();

for (int i = 0; i < words.length - 1; i++) {
for (int j = 0; j < Math.min(words[i].length(), words[i + 1].length()); j++) {
if (words[i].charAt(j) != words[i + 1].charAt(j)) {
String correctOrder = "" + words[i].charAt(j) + words[i + 1].charAt(j);
String reverseOrder = "" + words[i + 1].charAt(j) + words[i].charAt(j);
if (!orders.contains(correctOrder)) {
orders.add(correctOrder);
}
if (orders.contains(reverseOrder))
return "";// there's a cycle in this alphabet, such an order does't exist
break;
}
}
}

//compute only for appeared letters
Set<Character> appearedLetters = new HashSet<>();
for(String word : words){
char[] chars = word.toCharArray();
for(char c : chars){
appearedLetters.add(c);
}
}

int[] indegree = new int[26];
// find every letter's indegree
for (String c : orders) {
indegree[c.charAt(1) - 'a']++;
}
// use a set to hold all zero indegree's char and put all of them into the queue first
Set<Character> zeroDegree = new HashSet<>();
Queue<Character> q = new LinkedList<Character>();
for (int i = 0; i < 26; i++) {
if (indegree[i] == 0 && appearedLetters.contains((char) (i + 'a'))) {
zeroDegree.add((char) (i + 'a'));
q.offer((char) (i + 'a'));
}
}

while (!zeroDegree.isEmpty()) {
Iterator<Character> it = zeroDegree.iterator();
char curr = it.next();
zeroDegree.remove(curr);
for (String order : orders) {
if (order.charAt(0) == curr) {
indegree[order.charAt(1) - 'a']--;
if (indegree[order.charAt(1) - 'a'] == 0) {
zeroDegree.add(order.charAt(1));
q.offer(order.charAt(1));
}
}
}
}

for(int i : indegree){
if(i != 0) return "";
}

StringBuilder sb = new StringBuilder();
while(!q.isEmpty()){
sb.append(q.poll());
}

return sb.toString();
}

 

Why it took me so long? What I learned from this?

  • First, I misunderstood the problem description: I thought that each word is sorted lexicographically!!! No!!! Actually it’s not!!! The problem statement says that the list of wordS are sorted lexicographically!!! So, it’s the relative order between the words that matter, NOT the order between the chars inside each word!!! The following attempt was the result of my misunderstanding, I was really happy that I’m almost there, only then I spotted that per my understanding, then the given example of wouldn’t have that order: “wertf”, instead, it should be “werft”, then I was about to post a question to admin, then it turned out that on Discuss, people had already asked about this: https://discuss.leetcode.com/topic/22395/the-description-is-wrong/2*/
  • Followed the pattern of solving topological sort of this one: https://fishercoder.com/2016/07/17/course-schedule-ii/ and https://fishercoder.com/2016/07/17/course-schedule/ I implemented the code for this problem, ran into a bug, I documented it here, a good finding and helped me deepened my understanding: https://fishercoder.com/2016/07/17/hashset-to-filter-duplicate-char-array/
  • Then you’ll need to remember to check if  each indegree becomes zero in the end, if not, that means there’s a cycle in the graph, then return an empty string in this case.

 

Advertisements

Course Schedule II

https://leetcode.com/problems/course-schedule-ii/

  • Cool! Following that idea, I wrote this one completely by myself, nice!
  • Idea:
    • use a queue to hold all zero-degree vertex
    • loop through all other vertices, whenever one vertex’s indegree becomes zero, offer it into the q
    • when finished iterating the set, make sure to check if all indegree[] equals to zero, if not, that means there’s a cycle within the graph, in that case, just return an empty array as the problem requires, otherwise, return vertices in the queue
public int[] findOrder(int numCourses, int[][] prerequisites) {

int[] indegree = new int[numCourses];
for(int i = 0; i < prerequisites.length; i++){
indegree[prerequisites[i][0]]++;
}

Set<Integer> zeroDegree = new HashSet();
Queue<Integer> q = new LinkedList<Integer>();
for(int i = 0; i < numCourses; i++){
if(indegree[i] == 0) {
zeroDegree.add(i);
q.offer(i);
}
}

while(!zeroDegree.isEmpty()){
Iterator<Integer> it = zeroDegree.iterator();
int course = it.next();
zeroDegree.remove(course);
for(int[] edge : prerequisites){
if(edge[1] == course){
indegree[edge[0]]--;
if(indegree[edge[0]] == 0){
zeroDegree.add(edge[0]);
q.offer(edge[0]);
}
}
}
}

for(int i = 0; i < numCourses; i++){
if(indegree[i] != 0) return new int[0];
}

int[] order = new int[numCourses];
int i = 0;
while(!q.isEmpty() && i < numCourses){
order[i] = q.poll();
i++;
}

return order;

}

 

Course Schedule

https://leetcode.com/problems/course-schedule/

  • This video is helpful: https://www.youtube.com/watch?v=ddTC4Zovtbc
  • Topological sort is: in a Directed Acyclic Graph, ordering of vertices of this graph such that for every edge (u,v) going from u to v, u should always before v in the ordering.
  • There could be multiple topological orders for one graph, as long as the relative order between every two connected vertices is right.
  • One typical application (apart from the course taking example) is in the building system, suppose we have a number of packages, and they have dependencies between each other, how does the build system know which ones should be built first since they’re dependencies of the rest?
    • The build system would build a graph for it first, then it’ll build the packages in the right order.
  • We usually can use a set to store visited vertices and use a stack to store topologically sorted vertices (when one vertex has its children completely visited, then this vertex could be put into the stack.)

Then I was trying to implement this idea to solve this problem, but didn’t figure out how to do the nested for loop or recursion, then I turned to this post: https://discuss.leetcode.com/topic/14684/java-ac-solution-with-top-sort which kind of does exactly does what that video explained:

  • use those vertices as indices of the array degree[], this is smart! Because it gives you the numCourses, esp. it starts from 1 to n-1, this is a strong hint that it could be used as array indices.
  • per the problem description, pair [0,1] means 1-> 0, means you’ll have to take course 1 first, in order to take course 0, thus, expressed in graph, 1 has zero in-degree, i.e. pair[0] = 1 and pair[1] = 0; this is how the degree[] array is initialized.
  • in the while loop, we iterate through each edge for every vertex that is in the zeroDegree set, try to see if there’s any edge that has that zero-degree vertex as prerequisite, if so, then decrement that vertex’s degree by 1 and then right after, we check if that vertex’s indegree becomes zero or not, if it’s zero, that means it could be put into the zeroDegree set and start looping through it when it’s its turn.
  • Pay special attention: if(prerequisites[row][0] == 0) zeroDegree.add(prerequisites[row][0]); must be put inside the first if statement.
public boolean canFinish(int numCourses, int[][] prerequisites) {
Set<Integer> zeroDegree = new HashSet<Integer>();
int[] degree = new int[numCourses];
for(int i = 0; i < prerequisites.length; i++){
degree[prerequisites[i][0]]++;
}
for(int i = 0; i < numCourses; i++){
if(degree[i] == 0) zeroDegree.add(i);
}
if(zeroDegree.isEmpty()) return false;//this means there's no starting point, a cycle must exist
while(!zeroDegree.isEmpty()){
Iterator<Integer> it = zeroDegree.iterator();
int course = it.next();
zeroDegree.remove(course);
for(int row = 0; row < prerequisites.length; row++){
if(prerequisites[row][1] == course) {
degree[prerequisites[row][0]]--;
if(degree[prerequisites[row][0]] == 0) zeroDegree.add(prerequisites[row][0]);
}
}
}
for(int i = 0; i < numCourses; i++){
if(degree[i] != 0) return false;
}
return true;
}