String lexicográficamente más grande para el orden del diccionario dado

Dada una array arr[] de N strings y un orden de string que representa el nuevo orden alfabético de la string. La tarea es encontrar la string lexicográficamente más grande según el orden dado.

Ejemplos:

Entrada: a[] = {“abc”, “abd”, “abz”}, orden = “abczdefghijklmnopqrstuvwxy” 
Salida: abd 
Explicación:
Compara dos palabras “abc”, “abd”, el primer carácter que no coincide es c, d en el orden, c viene antes de d por lo que abd es el más grande entre ellos. 
Del mismo modo, compare abd y abz.

Entrada: arr[] = {“abc”, “abdz”, “abd”}, orden = “abcdefghijklmnopqrstuvwxyz”
Salida: abdz
Explicación:
Entre todas las strings dadas, abdz es la más grande.

Enfoque ingenuo: la idea es verificar cada string si es lexicográficamente la más grande entre las strings dadas o no. En caso afirmativo, imprima esa string; de lo contrario, verifique la siguiente string.

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: la idea es implementar una función de comparación de acuerdo con el orden de string dado para encontrar la string que es lexicográficamente más grande. A continuación se muestran los pasos:

1. Cree un mapa para almacenar el índice del carácter en el orden de string dado.
2. Considere la primera string de la array como la string lexicográficamente más grande como ans .
3. Ahora recorra la string dada en el rango [1, N] y compare cada string con la string ans usando los índices almacenados en el mapa.
4. Siga actualizando la string lexicográficamente más grande en el paso anterior e imprima la string.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h> 
using namespace std; 
   
int compare(string word1, string word2,
            int order[]);
             
// Find the lexicographically
// largest string
string largestString(string a[], int n,
                     string order)
{
     
    // Create a map of characters
    int map[26];
 
    // Value of each character is
    // string is given priority
    // according to their occurrence
    // in the string
    for(int i = 0; i < order.length(); i++)
        map[order[i] - 'a'] = i;
 
    // Take first String as maximum
    string ans = a[0];
 
    for(int i = 1; i < n; i++)
    {
         
        // Compare two strings each time
        if (compare(ans, a[i], map) < 0)
     
            // Update answer
            ans = a[i];
    }
    return ans;
}
 
// Implement compare function
// to get the dictionary order
int compare(string word1, string word2,
            int order[])
{
    int i = 0, j = 0, charcompareval = 0;
 
    while (i < word1.length() &&
           j < word2.length())
    {
         
        // Compare each char
        // according to the order
        charcompareval = order[word1[i] - 'a'] -
                         order[word2[i] - 'a'];
     
        // Find the first non matching
        // character in the string
        if (charcompareval != 0)
            return charcompareval;
             
        i++;
        j++;
    }
 
    // If one word is prefix of
    // other return shortest word
    if (charcompareval == 0)
        return (word1.length() -
                word2.length());
    else
        return charcompareval;
}
 
// Driver Code
int main()
{
    int n = 3;
 
    // Given array of strings arr
    string arr[] = { "abc", "abd", "abz" };
 
    // Given order of string
    string order = "abczdefghijklmnopqrstuvwxy";
 
    // Function call
    string ans = largestString(arr, n, order);
 
    cout << ans;
     
    return 0;
}
 
// This code is contributed by rutvik_56

// Java program for the above approach
 
import java.util.*;
public class Main {
 
    // Find the lexicographically
    // largest string
    public static String
    largestString(String[] a, int n,
                String order)
    {
        // Create a map of characters
        int map[] = new int[26];
 
        // Value of each character is
        // string is given priority
        // according to their occurrence
        // in the string
        for (int i = 0; i < order.length(); i++)
            map[order.charAt(i) - 'a'] = i;
 
        // Take first String as maximum
        String ans = a[0];
 
        for (int i = 1; i < n; i++) {
 
            // Compare two strings each time
            if (compare(ans, a[i], map) < 0)
 
                // Update answer
                ans = a[i];
        }
        return ans;
    }
 
    // Implement compare function
    // to get the dictionary order
    public static int
    compare(String word1, String word2,
            int[] order)
    {
        int i = 0, j = 0, charcompareval = 0;
 
        while (i < word1.length()
            && j < word2.length()) {
 
            // Compare each char
            // according to the order
            charcompareval
                = order[word1.charAt(i) - 'a']
                - order[word2.charAt(i) - 'a'];
 
            // Find the first non matching
            // character in the string
            if (charcompareval != 0)
 
                return charcompareval;
            i++;
            j++;
        }
 
        // If one word is prefix of
        // other return shortest word
        if (charcompareval == 0)
            return (word1.length()
                    - word2.length());
        else
            return charcompareval;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int n = 3;
 
        // Given array of strings arr
        String arr[] = { "abc", "abd", "abz" };
 
        // Given order of string
        String order
            = "abczdefghijklmnopqrstuvwxy";
 
        // Function call
        String ans
            = largestString(arr, n, order);
 
        System.out.println(ans);
    }
}

# Python3 program for the above approach
 
# Find the lexicographically
# largest string
def largestString(a, n, order):
 
    # Create a map of characters
    map = [0] * 26
 
    # Value of each character is
    # string is given priority
    # according to their occurrence
    # in the string
    for i in range(len(order)):
            map[ord(order[i]) - ord('a')] = i
 
    # Take first String as maximum
    ans = a[0]
 
    for i in range(1, n):
         
        # Compare two strings each time
        if (compare(ans, a[i], map) < 0):
 
            # Update answer
            ans = a[i]
         
    return ans
 
# Implement compare function
# to get the dictionary order
def compare(word1, word2, order):
 
    i = 0
    j = 0
    charcompareval = 0;
 
    while (i < len(word1) and
        j < len(word2)):
 
        # Compare each char
        # according to the order
        charcompareval = (order[ord(word1[i]) - ord('a')] -
                        order[ord(word2[i]) - ord('a')])
 
        # Find the first non matching
        # character in the string
        if (charcompareval != 0):
            return charcompareval
             
        i += 1
        j += 1
 
    # If one word is prefix of
    # other return shortest word
    if (charcompareval == 0):
        return (len(word1) - len(word2))
    else:
        return charcompareval
     
# Driver Code
if __name__ == "__main__":
 
    n = 3
 
    # Given array of strings arr
    arr = [ "abc", "abd", "abz" ]
 
    # Given order of string
    order = "abczdefghijklmnopqrstuvwxy"
 
    # Function call
    ans = largestString(arr, n, order)
     
    print(ans)
 
# This code is contributed by chitranayal

// C# program for the above approach
using System;
class GFG{
 
// Find the lexicographically
// largest string
public static String largestString(String[] a, int n,
                                    String order)
{
    // Create a map of characters
    int []map = new int[26];
 
    // Value of each character is
    // string is given priority
    // according to their occurrence
    // in the string
    for (int i = 0; i < order.Length; i++)
    map[order[i] - 'a'] = i;
 
    // Take first String as maximum
    String ans = a[0];
 
    for (int i = 1; i < n; i++)
    {
 
    // Compare two strings each time
    if (compare(ans, a[i], map) < 0)
 
        // Update answer
        ans = a[i];
    }
    return ans;
}
 
// Implement compare function
// to get the dictionary order
public static int compare(String word1,
                            String word2,
                            int[] order)
{
    int i = 0, j = 0, charcompareval = 0;
 
    while (i < word1.Length &&
        j < word2.Length)
    {
 
    // Compare each char
    // according to the order
    charcompareval = order[word1[i] - 'a'] -
                    order[word2[i] - 'a'];
 
    // Find the first non matching
    // character in the string
    if (charcompareval != 0)
 
        return charcompareval;
    i++;
    j++;
    }
 
    // If one word is prefix of
    // other return shortest word
    if (charcompareval == 0)
    return (word1.Length -
            word2.Length);
    else
    return charcompareval;
}
 
// Driver Code
public static void Main(String []args)
{
    int n = 3;
 
    // Given array of strings arr
    String []arr = { "abc", "abd", "abz" };
 
    // Given order of string
    String order = "abczdefghijklmnopqrstuvwxy";
 
    // Function call
    String ans = largestString(arr, n, order);
 
    Console.WriteLine(ans);
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// Javascriptam for the above approach
 
// Find the lexicographically
// largest string
function largestString(a, n, order)
{
     
    // Create a map of characters
    let map = new Array(26);
 
    // Value of each character is
    // string is given priority
    // according to their occurrence
    // in the string
    for(let i = 0; i < order.length; i++)
        map[order[i].charCodeAt(0) -
                 'a'.charCodeAt(0)] = i;
 
    // Take first String as maximum
    let ans = a[0];
 
    for(let i = 1; i < n; i++)
    {
         
        // Compare two strings each time
        if (compare(ans, a[i], map) < 0)
 
            // Update answer
            ans = a[i];
    }
    return ans;
}
 
// Implement compare function
// to get the dictionary order
function compare(word1, word2, order)
{
    let i = 0, j = 0, charcompareval = 0;
   
        while (i < word1.length &&
               j < word2.length)
        {
             
            // Compare each char
            // according to the order
            charcompareval = order[word1[i].charCodeAt(0) -
                                        'a'.charCodeAt(0)] -
                             order[word2[i].charCodeAt(0) -
                                        'a'.charCodeAt(0)];
   
            // Find the first non matching
            // character in the string
            if (charcompareval != 0)
                return charcompareval;
                 
            i++;
            j++;
        }
   
        // If one word is prefix of
        // other return shortest word
        if (charcompareval == 0)
            return (word1.length - word2.length);
        else
            return charcompareval;
}
 
// Driver Code
let n = 3;
let arr = [ "abc", "abd", "abz" ];
let order = "abczdefghijklmnopqrstuvwxy";
let ans = largestString(arr, n, order);
 
document.write(ans);
 
// This code is contributed by avanitrachhadiya2155
 
</script>

abd

Complejidad de tiempo: O(N *max_word_length) Espacio
auxiliar : O(1)