Ninja and Alien Language Order Problem

An alien dropped its dictionary while visiting Earth. The Ninja wants to determine the order of characters used in the alien language, based on the given list of words from the alien's dictionary.

Example:

Input:
words = ["baa", "abcd", "abca", "cab", "cad"]
Output:
Order: "bdac"
Explanation:

The order of characters is derived from the following constraints based on the words' order:
"baa" before "abcd": 'b' comes before 'a'.
"abcd" before "abca": 'd' comes before 'a'.
Resulting in the order 'b', 'd', 'a', 'c'.

Constraints:

  • The list of words may have more than one valid order; return the smallest lexicographical order.
  • Return an empty string if there is no valid order.
  • 1 <= T <= 10
  • 1 <= N <= 300
  • 0 <= size of a word <= 100
  • Time limit: 1 sec
AnswerBot
2d

Determine the order of characters in an alien language based on a list of words from the alien's dictionary.

  • Create a graph data structure to represent the relationships between characters in the words...read more

Help your peers!
Add answer anonymously...
Accenture Associate Software Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter