Bigggg Alien ahhh Decoding The “Alien Dictionary” Through One More Kahn’s Algorithm Lexicographical.

Demo of what we are going to do

Introduction:
I think no need for an introduction to this problem because I’ve already solved the miniature problem in the last blog (Blog link) explained with the detailed visual and what is the lesicographical means as well and that one easy tag problem so I will 200% ensure you can easily understood what’s core of the concept so please if you haven’t check it out so far please please stronly recommanded eyes at once

Decoding the question:

First, we decode what they are asking and what they are expecting from us simply they are given an N set of words with a sorted dictionary of alien language so no worries about gibberish, our task is to find the order of the characters in the alien language — — → order which means simple in our human has some orders like a b c d e f g h I j k l m n o p ……. Z Okay as like we need to find what’s the alien order Just wait I’ll explain visually

Question decoding

Algorithm Discussion:

If you have seen the above image I hope you know what they are asking If you haven’t checked it out please just scroll up to see the image at once because I described deeply what they are expecting from us okay It seems like who wants to comes before and next, this phrase looks we’ve already familiar with it somewhere yes you heard me right Topo sorting algorithm which means Kahn’s algorithm is better for arrange Topo sorting so we are going to make a bridge between to aliens and Kahn’s if you don’t know about Kahn’s go back to our previous blogs I’ll described deeply with visually you will master it I’ll dropping the link as well blog link so I can hear you hey marudhu what will be first process to approach this one wait karo

• First, They’ve been clearly mentioned K = 4 which is the first 4 alphabets from our human dictionary these words all are already sorted so don’t mess up with anything order of words first extracts each letter from the sorted words then compare with that if both strings are not equal then make an adjacency list with that two letters I’ve already told you they are already sorted so just compare if not equal, how do we store the string in the particular index when comes to index we need to 0 to N okay, how marudhu simple I hope you all well known ASCII table with the help of we can convert the particular string into index am I right after doing all the process with the index we can easily getting those particular alphabets back to as per the what we got answer.
• B and A string to convert index B — — → 1 and A — — → 0 which means 1 connected with 0 still confusing [ [ ] [0] [ ] [ ] ] our adj list looks like after doing all the Kahn’s process 1 — → B and 0 — → A we can easily getting the alphabets from the ASCII table.
• With the adjacency list, we all know what to do then the classical process of Kahn’s find who has the 0 Indegree push into the queue if any adjacent has that particular node move onto it and push into the queue as well we should do till all nodes became 0 Indegree then extract the data from the queue show the list to alien this is your order of dictionary please follow the order while speaking with among your family okay if you have still doesn’t make sense just wait let’s see with visually.

Visual Representation:

The core of the problem

Code Showcase:

class Solution {
  // usual Kahn's process if you don't know just go back read the kahn's blog.
  kahnsAlgo(v, adj) {
    let indegree = new Array(v).fill(0);
    let queue = []; // first in first out
    for (let i = 0; i < v; i++) {
      for (let degreeIncreasing of adj[i]) {
        indegree[degreeIncreasing]++;
      }
    }
    for (let j = 0; j < v; j++) {
      if (indegree[j] === 0) {
        queue.push(j);
      }
    }
    let kahnstopo = [];
    while (queue.length !== 0) {
      let vertex = queue.shift();
      kahnstopo.push(vertex);

      for (let remove of adj[vertex]) {
        indegree[remove]--;
        if (indegree[remove] === 0) {
          queue.push(remove);
        }
      }
    }
    return kahnstopo;
  }

  findOrder(dict, n, k) {
    let createAdjList = new Array(k);
    for (let i = 0; i < k; i++) {
      createAdjList[i] = [];
    }
    console.log(createAdjList);

    for (let i = 0; i < n - 1; i++) {
      // loop for extract words from the array
      let strOne = dict[i];
      let strTwo = dict[i + 1];

      let len = Math.min(strOne.length, strTwo.length);
      // after extracted words fetch each words from that extracted words.
      for (let j = 0; j < len; j++) {
        if (strOne[j] != strTwo[j]) {
          createAdjList[strOne[j].charCodeAt(0) - 97].push(
            strTwo[j].charCodeAt(0) - 97
          );
          break;
        }
      }
    }
    // this one last process after doing all the kahn's process okay don't see at initially...
    let topo = this.kahnsAlgo(k, createAdjList);
    // this one more efficient method as well as you can directly change the string example this one escape from the error time limit exceeded
    let changeString = [];
    for (let changeChar of topo) {
      changeString.push(String.fromCharCode(changeChar + 97));
    }
    return changeString.join(" ");
  }
}

let alienDic = ["baa", "abcd", "abca", "cab", "cad"];
let nOfLength = 5;
let standardAlbha = 4;

const data = new Solution();
let output = data.findOrder(alienDic, nOfLength, standardAlbha);
console.log(output);

Thanksgiving:

Thanks for reading so far, if you are in the title space you will master any string problem finally we made one good thing for aliens we got the alien order so they will be happy just kidding thanks again please hit the follow button and don’t forget to the hit applaud button as well and hit one more bell icon button there beside of the follow button just click it you will get immediate notification if you’d any question on your mind just drop the command I’ll try to sort it out thanks a ton.