I just have an phone interview with Apple, but I did not really good explanation for this question. Therefore, I want to "re-eat" this question. Upvote my solution if you like it: https://leetcode.com/problems/alien-dictionary/discuss/577291/python-easy-topological-sort-solution
First of all, for this kind of question, you should know it belongs to Topological Sort. Why? 1) you need to solve it based on the direct graph, 2) it has ordered for each vertex in the graph. Thus, once you find information like need graph and exist order in question description. Then, you need to consider from Topological Sort. Next, use your Topological Sort templet to solve it: 1) build a directed graph with degree 2) use BFS to prune graph from low degree vertex to high degree vertex. 3) check if it is the acyclic directed graph.
In LeetCode, there is one new test case "["abc","ab"]" that I use my templete cannot pass it. Therefore, I add one condition to hack it because this is not vaild input, I should return "":
if not value_graph and len(words) == 2 and len(words[0]) > len(words[1]):
return resSame question: https://leetcode.com/problems/course-schedule-ii/ and https://leetcode.com/problems/course-schedule/
Time complexity: O(v+e)
Space complexity: O(v)
import collections
class Solution(object):
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
data_value_dict = set(''.join(words))
degree_value_dict = {x: 0 for x in data_value_dict}
value_graph = collections.defaultdict(list)
value_list = collections.deque()
res = ''
for pair in zip(words, words[1:]):
for x, y in zip(*pair):
if x != y:
value_graph[x].append(y)
degree_value_dict[y] += 1
break
if not value_graph and len(words) == 2 and len(words[0]) > len(words[1]):
return res
for key, value in degree_value_dict.items():
if not value:
value_list.append(key)
while value_list:
temp_value = len(value_list)
for _ in range(temp_value):
a = value_list.popleft()
res += a
for b in value_graph[a]:
degree_value_dict[b] -= 1
if not degree_value_dict[b]:
value_list.append(b)
if set(res) != data_value_dict:
res = ''
return resI also post my 207. Course Schedule solution, so you can see I use templete to solve both questions.
import collections
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
value_graph = collections.defaultdict(list)
degree_value_list = [0] * numCourses
value_list = collections.deque()
count = 0
res = False
for a, b in prerequisites:
value_graph[a].append(b)
degree_value_list[b] += 1
for i in range(numCourses):
if degree_value_list[i] == 0:
value_list.append(i)
while value_list:
temp_value = len(value_list)
for _ in range(temp_value):
a = value_list.popleft()
count += 1
for b in value_graph[a]:
degree_value_list[b] -= 1
if not degree_value_list[b]:
value_list.append(b)
if count == numCourses:
res = True
return res