Lexicographic order coding pattern

Lexicographic sorting compares strings character by character until a difference is found. If one string is shorter than the other, the shorter string is considered “less than” the longer one. This means that shorter strings always precede longer strings in lexicographic order.

Following is comparator function to show the Lexicographic sorting order.

const comparator = (word1, word2) => {
  const m = word1.length;
  const n = word2.length;
  let i=0;
  while(i < m && i < n) {
    if(word1[i] === word2[i]) {
      i++;
      continue;
    }
    // found first different char
    return word1[i].charCodeAt(0) - word2[i].charCodeAt(0);
  }
  // On exhaust fiding the diff, apply length based order
  return m - n;
}

Let’s do few problems which uses Lexicographic concept.

953. Verifying an Alien Dictionary

https://leetcode.com/problems/verifying-an-alien-dictionary/description/

In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.

Example 1:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Approach

Apply lexicographical sorting order.

/**
 * @param {string[]} words
 * @param {string} order
 * @return {boolean}
 */
var isAlienSorted = function (words, order) {
    const map = new Map();
    for (let i = 0; i < order.length; i++) {
        map.set(order[i], i);
    }
    const comparator = (word1, word2) => {
        const m = word1.length;
        const n = word2.length;
        let i = 0;
        while (i < m && i < n) {
            const a = word1[i];
            const b = word2[i];
            if (a === b) {
                i++;
                continue;
            }
            return map.get(a) - map.get(b);
        }
        return m - n;
    }
    // Verify order
    for (let i = 1; i < words.length; i++) {
        if (comparator(words[i - 1], words[i]) > 0) {
            return false;
        }
    }
    return true;
};

269. Alien Dictionary

https://leetcode.com/problems/alien-dictionary/description/

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary. Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language.

If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "".

Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language’s rules. If there are multiple solutions, return any of them.

Example 1:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

Approach

1. Build directed graph for every chars in the words as node.
2. Compare every two consecutive words and define edge for nodes in the graph.
3. We can return early if these two words doesn’t follow the basics of lexicographic sorting order. Rule #1: len(word1) ≤ len(word2). Rule#2: word1 should not be starts with word2
4. Apply topological sorting.
5. If cycle exist then topological sorting is not feasible therefore return empty string.

Note: Since there are multiple algorithm to run the topological sort therefore we can also write multiple versions.

Topological sorting 1 # Using arrival/departure time

const dfs = (graph, node, visited, results, arrival, departure, timer) => {
    // mark node as visited
    visited.set(node, true);
    
    // update arrival time
    arrival.set(node, timer.ts++);
    
    // process all neighbors
    for (const neighbor of graph.get(node)) {
        // if not visited then launch dfs
        if(!visited.has(neighbor)) {
            if(dfs(graph, neighbor, visited, results, arrival, departure, timer)){
                return true;
            }
        } else {
            // if already visited, check for backedge i.e. if departure time of node is not set
            if(!departure.has(neighbor)) {
                return true;
            }
        }
    }
    // update departure time
    departure.set(node, timer.ts++);
    
    // Add node into results for topological order
    results.push(node);
    
    return false;
}
const buildGraph = words => {
    const graph = new Map();
    const n = words.length;
    
    // Initialize graph for all node
    for (const word of words) {
        for (const node of word) {
            if(!graph.has(node)) {
                graph.set(node, []);
            }
        }
    }
    
    // Find edges
    for (let i=0; i < n -1; i++) {
        const word1 = words[i];
        const word2 = words[i+1];
        
        // if doesn't follow lexicographical order i.e. len of word1 > word2 and word2 is substring of word1
        if(word1.length > word2.length && word1.startsWith(word2)) {
            return new Map();
        }
        
        // get first diff char to establish edge with A->B i.e. A is smaller than B.
        for (let j = 0; j < Math.min(word1.length, word2.length); j++) {
            if(word1[j] !== word2[j]) {
                graph.get(word1[j]).push(word2[j]);
                break;
            }
        }
    }
    return graph;
}
/**
 * @param {string[]} words
 * @return {string}
 */
var alienOrder = function(words) {
    const graph = buildGraph(words);
    const visited = new Map();
    const arrival = new Map();
    const departure = new Map();
    const results = [];
    const timer = {ts: 0};
    // launch dfs multiple times to cover all components
    for (const [node] of graph) {
        if(!visited.has(node)) {
            if(dfs(graph, node, visited, results, arrival, departure, timer)) {
                // return empty if cycle exist
                return '';                
            }            
        }
    }

    return results.reverse().join('');
};

Topological sorting 2 # Using 1: UNVISITED, 2: EXPLORED, 3: VISITED state

const dfs = (graph, node, visited, results) => {
    // mark node as 2: EXPLORED
    visited.set(node, 2);
    // process all neighbors
    for (const neighbor of graph.get(node)) {
        // if not visited then launch dfs
        if (visited.get(neighbor) === 1) { // Not yet explored
            if (dfs(graph, neighbor, visited, results)) {
                return true;
            }
        } else {
            // back edge on EXPLORED
            if (visited.get(neighbor) === 2) {
                return true;
            }
        }
    } 
    // Mark node as VISITED
    visited.set(node, 3);
    // Add node into results for topological order
    results.push(node);
    return false;
}
const buildGraph = words => {
    const graph = new Map();
    const n = words.length;

    // Initialize graph for all node
    for (const word of words) {
        for (const node of word) {
            if (!graph.has(node)) {
                graph.set(node, []);
            }
        }
    }

    // Find edges
    for (let i = 0; i < n - 1; i++) {
        const word1 = words[i];
        const word2 = words[i + 1];

        // if doesn't follow lexicographical order i.e. len of word1 > word2 and word2 is substring of word1
        if (word1.length > word2.length && word1.startsWith(word2)) {
            return new Map();
        }

        // get first diff char to establish edge with A->B i.e. A is smaller than B.
        for (let j = 0; j < Math.min(word1.length, word2.length); j++) {
            if (word1[j] !== word2[j]) {
                graph.get(word1[j]).push(word2[j]);
                break;
            }
        }
    }
    return graph;
}
/**
 * @param {string[]} words
 * @return {string}
 */
var alienOrder = function (words) {
    const graph = buildGraph(words);
    const visited = new Map();
    // Initialized all node as 1:UNVISITED
    for (const [node] of graph) {
        visited.set(node, 1);
    }
    const results = [];
    // launch dfs multiple times to cover all components
    for (const [node] of graph) {
        if (visited.get(node) === 1) {
            if (dfs(graph, node, visited, results)) {
                // return empty if cycle exist
                return '';
            }
        }
    }
    return results.reverse().join('');
};

Topological sorting 3 # Using BFS on an acyclic graph (Kahn’s algo)

const buildGraph = words => {
    const graph = new Map();
    const n = words.length;
    const indegree = new Map();
    // Initialize graph for all node
    for (const word of words) {
        for (const node of word) {
            if (!graph.has(node)) {
                graph.set(node, []);
                indegree.set(node, 0);
            }
        }
    }

    // Find edges
    for (let i = 0; i < n - 1; i++) {
        const word1 = words[i];
        const word2 = words[i + 1];

        // if doesn't follow lexicographical order i.e. len of word1 > word2 and word2 is substring of word1
        if (word1.length > word2.length && word1.startsWith(word2)) {
            return [new Map(), new Map()];
        }

        // get first diff char to establish edge with A->B i.e. A is smaller than B.
        for (let j = 0; j < Math.min(word1.length, word2.length); j++) {
            const u = word1[j];
            const v = word2[j];
            if (u !== v) {
                // Edge from u -> v
                graph.get(u).push(v);
                // Capture indegree as well
                indegree.set(v, indegree.get(v) + 1)
                break;
            }
        }
    }
    return [graph, indegree];
}
/**
 * @param {string[]} words
 * @return {string}
 */
var alienOrder = function (words) {
    const [graph, indegree] = buildGraph(words);
    const results = [];
    const queue = [];
    // Initialize queue with all node with indegree = 0
    for (const [node, degree] of indegree) {
        if (degree === 0) {
            queue.push(node);
        }
    }
    while (queue.length > 0) {
        const node = queue.shift();
        results.push(node); // Capture topo sort
        for (const neighbor of graph.get(node)) {
            if (indegree.get(neighbor) > 0) {
                indegree.set(neighbor, indegree.get(neighbor) - 1);
                // Add into queue only if indegree become zero
                if (indegree.get(neighbor) === 0) {
                    queue.push(neighbor);
                }
            }
        }
    }
    // In case of cycle
    if(results.length !== graph.size) {
        return '';
    }
    return results.join('');
};

1641. Count Sorted Vowel Strings

https://leetcode.com/problems/count-sorted-vowel-strings/description/

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Example 1:

Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Approach

1. Goal here is to count lexicographically sorted string s
2. It means to generate let’s say two length string ea is not a valid string as e comes after a
3. f(i, n) return count of string of length exactly n starting with vowel at index i.
4. At xxxxx_ to place at ith position starting with vowel i , we have chioces of i.....5 vowels.

We can write following recursion relationship.

f(i,n) = count of string started with vowel at index i with length n
f(i,n) = 1 with n=0 i.e. empty is possible with 0 length
f(i,n) = sum(
      f(j,n-1) where j=i.....5
)

Following is code for reference.

const recursion = (i, n, dp) => {
    // base case
    if(n === 0) {
        return 1;
    }
    const key = `${i}-${n}`;
    if(dp.has(key)) {
        return dp.get(key);
    }
    // number of strings started with vowel
    let total = 0;
    for (let j= i; j < 5; j++) {
        total += recursion(j, n-1, dp);
    }
    dp.set(key, total);
    return total;
}
/**
 * @param {number} n
 * @return {number}
 */
var countVowelStrings = function(n) {
    const dp = new Map();
    return recursion(0, n, dp); 
};

Happy coding !!!