Ordenar una array de strings (o palabras) usando Trie – Part 1

Dada una serie de strings, imprímalas en orden alfabético (diccionario). Si hay duplicados en la array de entrada, debemos imprimirlos solo una vez.

Ejemplos: 

Input : "abc", "xy", "bcd"
Output : abc bcd xy         

Input : "geeks", "for", "geeks", "a", "portal", 
        "to", "learn", "can", "be", "computer", 
        "science", "zoom", "yup", "fire", "in", "data"
Output : a be can computer data fire for geeks
         in learn portal science to yup zoom

Trie es una estructura de datos eficiente utilizada para almacenar datos como strings. Para imprimir la string en orden alfabético, primero debemos insertarla en el trie y luego realizar un recorrido de preorden para imprimir en orden alfabético.

Implementación:

// C++ program to sort an array of strings
// using Trie
#include <bits/stdc++.h>
using namespace std;
 
const int MAX_CHAR = 26;
 
struct Trie {
 
    // index is set when node is a leaf
    // node, otherwise -1;
    int index;
 
    Trie* child[MAX_CHAR];
 
    /*to make new trie*/
    Trie()
    {
        for (int i = 0; i < MAX_CHAR; i++)
            child[i] = NULL;
        index = -1;
    }
};
 
/* function to insert in trie */
void insert(Trie* root, string str, int index)
{
    Trie* node = root;
 
    for (int i = 0; i < str.size(); i++) {
 
        /* taking ascii value to find index of
          child node */
        char ind = str[i] - 'a';
 
        /* making new path if not already */
        if (!node->child[ind])
            node->child[ind] = new Trie();
 
        // go to next node
        node = node->child[ind];
    }
 
    // Mark leaf (end of word) and store
    // index of word in arr[]
    node->index = index;
}
 
/* function for preorder traversal */
bool preorder(Trie* node, string arr[])
{
    if (node == NULL)
        return false;
 
    for (int i = 0; i < MAX_CHAR; i++) {
        if (node->child[i] != NULL) {
 
            /* if leaf node then print key*/
            if (node->child[i]->index != -1)
                cout << arr[node->child[i]->index] << endl;
 
            preorder(node->child[i], arr);
        }
    }
}
 
void printSorted(string arr[], int n)
{
    Trie* root = new Trie();
 
    // insert all keys of dictionary into trie
    for (int i = 0; i < n; i++)
        insert(root, arr[i], i);
 
    // print keys in lexicographic order
    preorder(root, arr);
}
 
// Driver code
int main()
{
    string arr[] = { "abc", "xy", "bcd" };
    int n = sizeof(arr) / sizeof(arr[0]);
    printSorted(arr, n);
    return 0;
}

// Java program to sort an array of strings using Trie
 
// Author : Rohit Jain
// GFG user_id : @rj03012002
 
import java.util.*;
 
class GFG {
 
    // Alphabet size
    static final int MAX_CHAR = 26;
 
    // trie node
    static class Trie {
 
        // index is set when node is a leaf
        // node, otherwise -1;
        int index;
 
        Trie child[] = new Trie[MAX_CHAR];
 
        /*to make new trie*/
        Trie()
        {
 
            for (int i = 0; i < MAX_CHAR; i++)
                child[i] = null;
            index = -1;
        }
    }
 
    /* function to insert in trie */
    static void insert(Trie root, String str, int index)
    {
 
        Trie node = root;
 
        for (int i = 0; i < str.length(); i++) {
            /* taking ascii value to find index of
          child node */
            int ind = str.charAt(i) - 'a';
 
            /* making new path if not already */
            if (node.child[ind] == null)
                node.child[ind] = new Trie();
 
            // go to next node
            node = node.child[ind];
        }
 
        // Mark leaf (end of word) and store
        // index of word in arr[]
        node.index = index;
    }
 
    /* function for preorder traversal */
    static boolean preorder(Trie node, String arr[])
    {
 
        if (node == null) {
 
            return false;
        }
 
        for (int i = 0; i < MAX_CHAR; i++) {
 
            if (node.child[i] != null) {
 
                /* if leaf node then print key*/
                if (node.child[i].index != -1) {
 
                    System.out.print(
                        arr[node.child[i].index] + " ");
                }
 
                preorder(node.child[i], arr);
            }
        }
        return false;
    }
 
    static void printSorted(String arr[], int n)
    {
 
        Trie root = new Trie();
 
        // insert all keys of dictionary into trie
        for (int i = 0; i < n; ++i) {
 
            insert(root, arr[i], i);
        }
 
        // print keys in lexicographic order
        preorder(root, arr);
    }
 
    public static void main(String[] args)
    {
 
        String arr[] = { "abc", "xy", "bcd" };
 
        int n = arr.length;
 
        printSorted(arr, n);
    }
}

# Python3 program to sort an array of strings
# using Trie
 
MAX_CHAR = 26
 
class Trie:
 
    # index is set when node is a leaf
    # node, otherwise -1;
    # to make new trie
    def __init__(self):
        self.child = [None for i in range(MAX_CHAR)]
        self.index = -1
     
 
# def to insert in trie
def insert(root,str,index):
 
    node = root
 
    for i in range(len(str)):
 
        # taking ascii value to find index of
        # child node
        ind = ord(str[i]) - ord('a')
 
        # making new path if not already
        if (node.child[ind] == None):
            node.child[ind] = Trie()
 
        # go to next node
        node = node.child[ind]
     
 
    # Mark leaf (end of word) and store
    # index of word in arr[]
    node.index = index
 
 
# function for preorder traversal
def preorder(node, arr):
 
    if (node == None):
        return False
 
    for i in range(MAX_CHAR):
        if (node.child[i] != None):
 
            # if leaf node then print key
            if (node.child[i].index != -1):
                print(arr[node.child[i].index])
 
            preorder(node.child[i], arr)
         
 
 
def printSorted(arr,n):
 
    root = Trie()
 
    # insert all keys of dictionary into trie
    for i in range(n):
        insert(root, arr[i], i)
 
    # print keys in lexicographic order
    preorder(root, arr)
 
 
# Driver code
 
arr = [ "abc", "xy", "bcd" ]
n = len(arr)
printSorted(arr, n)
 
# This code is contributed by shinjanpatra

<script>
 
// JavaScript program to sort an array of strings
// using Trie
 
const MAX_CHAR = 26;
 
class Trie {
 
    // index is set when node is a leaf
    // node, otherwise -1;
    /*to make new trie*/
    constructor()
    {
        this.child = new Array(MAX_CHAR).fill(null);
        this.index = -1;
    }
}
 
/* function to insert in trie */
function insert(root,str,index)
{
    let node = root;
 
    for (let i = 0; i < str.length; i++) {
 
        /* taking ascii value to find index of
        child node */
        let ind = str.charCodeAt(i) - 'a'.charCodeAt(0);
 
        /* making new path if not already */
        if (node.child[ind] == null)
            node.child[ind] = new Trie();
 
        // go to next node
        node = node.child[ind];
    }
 
    // Mark leaf (end of word) and store
    // index of word in arr[]
    node.index = index;
}
 
/* function for preorder traversal */
function preorder(node, arr)
{
    if (node == null)
        return false;
 
    for (let i = 0; i < MAX_CHAR; i++) {
        if (node.child[i] != null) {
 
            /* if leaf node then print key*/
            if (node.child[i].index != -1)
                document.write(arr[node.child[i].index],"</br>");
 
            preorder(node.child[i], arr);
        }
    }
}
 
function printSorted(arr,n)
{
    let root = new Trie();
 
    // insert all keys of dictionary into trie
    for (let i = 0; i < n; i++)
        insert(root, arr[i], i);
 
    // print keys in lexicographic order
    preorder(root, arr);
}
 
// Driver code
 
let arr = [ "abc", "xy", "bcd" ];
let n = arr.length;
printSorted(arr, n);
 
// This code is contributed by shinjanpatra
 
</script>

abc
bcd
xy

Complejidad temporal: O(n)
Espacio auxiliar: O(n)

Este artículo es una contribución de Pranav . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.