educative.io

Incorrect Output in leetCide

Courses
,
#1

Solution is not working on leetcode platform.

#2

I had to update build the graph step as follow:
// Step - 2 => build the graph
for (int i = 0; i < words.length - 1; i++) {
String word1 = words[i], word2 = words[i+1];
// Check that word2 is not a prefix of word1.
if (word1.length() > word2.length() && word1.startsWith(word2)) {
return “”;
}
for (int j = 0; j < Math.min(word1.length(), word2.length()); j++) {
char parent = word1.charAt(j);
char child = word2.charAt(j);
if(parent != child) { // if the two characters are different
graph.get(parent).add(child); // Add it different character as a child of parent
inDegree.put(child, inDegree.get(child) + 1); // increment indegree
break; // When we encounter first differ character
}

                }
            }
1 Like
#3

Thank you, Neel!! you’re the best !!!

#4

Python version ( words on leetcode)

def find_order(words):
        indegree = {char:0 for word in words for char in word}
        adj_list = defaultdict(set)
        
        for word1, word2 in zip(words,words[1:]):
            for c1, c2 in zip(word1, word2):
                if c1 != c2:
                    if c2 not in adj_list[c1]:
                        adj_list[c1].add(c2)
                        indegree[c2] += 1
                    break
            else: # if break is never reached -> c1 and c2 are the same till now
                # check the second word is not a prefix of the first word
                if len(word1) > len(word2):
                    return ""
        queue = [c for c in indegree if indegree[c]==0]
        result = []
        while queue:
            char = queue.pop(0)
            result.append(char)
            for nei_char in adj_list[char]:
                indegree[nei_char] -= 1
                if indegree[nei_char] == 0:
                    queue.append(nei_char)
        if len(result) != len(indegree):
            return ""
        return "".join(result)

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Alien Dictionary (hard) - Grokking the Coding Interview: Patterns for Coding Questions