educative.io

Incorporating some Python Features into Solution (zip, defaultdict)

Courses
,
#1 
from collections import defaultdict, deque


def find_order(words):

    adjlist = defaultdict(list)
    indegrees = defaultdict(int)

    for i, word in enumerate(words[:-1]):
        word2 = words[i + 1]

        for c1, c2 in zip(word, word2):
            # Note: zip ignores shorter word chars
            if c1 != c2:
                adjlist[c1].append(c2)
                indegrees[c2] += 1

                if c1 not in indegrees:
                    indegrees[c1] = 0
                break # only process one difference

    sources = deque([c for (c, deg) in indegrees.items() if deg == 0])
    ordering = []

    while sources:
        cur_source = sources.popleft()
        ordering.append(cur_source)

        for child in adjlist[cur_source]:
            indegrees[child] -= 1
            if indegrees[child] == 0:
                sources.append(child)

    return "".join(ordering)

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/6610306698575872

1 Like
#2

Hi @Akshay_Goel,

There are multiple ways to solve one problem. The algorithm, we are implementing is without the deafultdict module.
Your code is working fine with the input. You can use your code for such problems but make sure to calculate the time complexity of your code. It will help you to choose the right and time-efficient code.

#3

Hi @Akshay_Goel! I love your solution! I we can use deque I don’t see why we cannot use defaultdict.

Just a detail: When there is not definitive order between some alphabets, your code doesn’t include it, while the “official” solution does. In the problem specification is not defined what to do, but I would say that any order that agrees with the encountered restrictions should be accepted. Examples:

find_order(["bac", "acb"])

Official: cba
Yours: ba
Acceptable: cba, bca, bac

find_order(["bac", "ba"])

Official: abc
Yours: “”
Acceptable: abc, acb, bac, bca, cab, cba

find_order(["a"])

Official: a
Yours: “”

And since we are optimizing, you should use a string for the result:
…
ordering = “”
…
ordering += cur_source
…
return ordering

:wink: