Dada una serie de strings, imprímalas en orden alfabético (diccionario). Si hay duplicados en la array de entrada, debemos imprimir todas las ocurrencias.
Ejemplos:
Input : arr[] = { "abc", "xyz", "abcd", "bcd", "abc" }
Output : abc abc abcd bcd xyz
Input : arr[] = { "geeks", "for", "geeks", "a", "portal",
"to", "learn" }
Output : a for geeks geeks learn portal to
Requisito previo: Trie | (Insertar y Buscar).
Enfoque: en la publicación anterior , se está ordenando una array de strings, imprimiendo solo una ocurrencia de strings duplicadas. En esta publicación, todas las ocurrencias de strings duplicadas se imprimen en orden lexicográfico. Para imprimir las strings en orden alfabético, primero debemos insertarlas en el trie y luego realizar un recorrido de preorden para imprimir en orden alfabético. Los Nodes de trie contienen una array index[] que almacena la posición de índice de todas las strings de arr[] que terminan en ese Node. Excepto el Node hoja de trie, todos los demás Nodes tienen el tamaño 0 para la array index[] .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation to sort an array
// of strings using Trie
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
struct Trie {
// 'index' vectors size is greater than
// 0 when node/ is a leaf node, otherwise
// size is 0;
vector<int> index;
Trie* child[MAX_CHAR];
/*to make new trie*/
Trie()
{
// initializing fields
for (int i = 0; i < MAX_CHAR; i++)
child[i] = NULL;
}
};
// function to insert a string 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 a 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 string) and store
// index of 'str' in index[]
(node->index).push_back(index);
}
// function for preorder traversal of trie
void preorder(Trie* node, string arr[])
{
// if node is empty
if (node == NULL)
return;
for (int i = 0; i < MAX_CHAR; i++) {
if (node->child[i] != NULL) {
// if leaf node then print all the strings
// for (node->child[i]->index).size() > 0)
for (int j = 0; j < (node->child[i]->index).size(); j++)
cout << arr[node->child[i]->index[j]] << " ";
preorder(node->child[i], arr);
}
}
}
// function to sort an array
// of strings using Trie
void printSorted(string arr[], int n)
{
Trie* root = new Trie();
// insert all strings of dictionary into trie
for (int i = 0; i < n; i++)
insert(root, arr[i], i);
// print strings in lexicographic order
preorder(root, arr);
}
// Driver program to test above
int main()
{
string arr[] = { "abc", "xyz", "abcd", "bcd", "abc" };
int n = sizeof(arr) / sizeof(arr[0]);
printSorted(arr, n);
return 0;
}
Java
// Java implementation
// to sort an array of
// strings using Trie
import java.util.*;
class Trie {
private Node rootNode;
/*to make new trie*/
Trie()
{
rootNode = null;
}
// function to insert
// a string in trie
void insert(String key, int index)
{
// making a new path
// if not already
if (rootNode == null)
{
rootNode = new Node();
}
Node currentNode = rootNode;
for (int i = 0;i < key.length();i++)
{
char keyChar = key.charAt(i);
if (currentNode.getChild(keyChar) == null)
{
currentNode.addChild(keyChar);
}
// go to next node
currentNode = currentNode.getChild(keyChar);
}
// Mark leaf (end of string)
// and store index of 'str'
// in index[]
currentNode.addIndex(index);
}
void traversePreorder(String[] array)
{
traversePreorder(rootNode, array);
}
// function for preorder
// traversal of trie
private void traversePreorder(Node node,
String[] array)
{
if (node == null)
{
return;
}
if (node.getIndices().size() > 0)
{
for (int index : node.getIndices())
{
System.out.print(array[index] + " ");
}
}
for (char index = 'a';index <= 'z';index++)
{
traversePreorder(node.getChild(index), array);
}
}
private static class Node {
private Node[] children;
private List<Integer> indices;
Node()
{
children = new Node[26];
indices = new ArrayList<>(0);
}
Node getChild(char index)
{
if (index < 'a' || index > 'z')
{
return null;
}
return children[index - 'a'];
}
void addChild(char index)
{
if (index < 'a' || index > 'z')
{
return;
}
Node node = new Node();
children[index - 'a'] = node;
}
List<Integer> getIndices()
{
return indices;
}
void addIndex(int index)
{
indices.add(index);
}
}
}
class SortStrings {
// Driver program
public static void main(String[] args)
{
String[] array = { "abc", "xyz",
"abcd", "bcd", "abc" };
printInSortedOrder(array);
}
// function to sort an array
// of strings using Trie
private static void printInSortedOrder(String[] array)
{
Trie trie = new Trie();
for (int i = 0;i < array.length;i++)
{
trie.insert(array[i], i);
}
trie.traversePreorder(array);
}
}
// Contributed by Harikrishnan Rajan
C#
// C# implementation
// to sort an array of
// strings using Trie
using System;
using System.Collections.Generic;
public class Trie
{
public Node rootNode;
/* to make new trie*/
public Trie()
{
rootNode = null;
}
// function to insert
// a string in trie
public void insert(String key, int index)
{
// making a new path
// if not already
if (rootNode == null)
{
rootNode = new Node();
}
Node currentNode = rootNode;
for (int i = 0;i < key.Length;i++)
{
char keyChar = key[i];
if (currentNode.getChild(keyChar) == null)
{
currentNode.addChild(keyChar);
}
// go to next node
currentNode = currentNode.getChild(keyChar);
}
// Mark leaf (end of string)
// and store index of 'str'
// in index[]
currentNode.addIndex(index);
}
public void traversePreorder(String[] array)
{
traversePreorder(rootNode, array);
}
// function for preorder
// traversal of trie
public void traversePreorder(Node node,
String[] array)
{
if (node == null)
{
return;
}
if (node.getIndices().Count > 0)
{
foreach (int index in node.getIndices())
{
Console.Write(array[index] + " ");
}
}
for (char index = 'a';index <= 'z';index++)
{
traversePreorder(node.getChild(index), array);
}
}
public class Node
{
public Node[] children;
public List<int> indices;
public Node()
{
children = new Node[26];
indices = new List<int>(0);
}
public Node getChild(char index)
{
if (index < 'a' || index > 'z')
{
return null;
}
return children[index - 'a'];
}
public void addChild(char index)
{
if (index < 'a' || index > 'z')
{
return;
}
Node node = new Node();
children[index - 'a'] = node;
}
public List<int> getIndices()
{
return indices;
}
public void addIndex(int index)
{
indices.Add(index);
}
}
}
public class SortStrings
{
// Driver code
public static void Main(String[] args)
{
String[] array = { "abc", "xyz",
"abcd", "bcd", "abc" };
printInSortedOrder(array);
}
// function to sort an array
// of strings using Trie
static void printInSortedOrder(String[] array)
{
Trie trie = new Trie();
for (int i = 0;i < array.Length;i++)
{
trie.insert(array[i], i);
}
trie.traversePreorder(array);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python implementation to sort an array
# of strings using Trie
from typing import List
MAX_CHAR = 26
class Trie:
def __init__(self) -> None:
# 'index' vectors size is greater than
# 0 when node/ is a leaf node, otherwise
# size is 0;
self.index = []
self.child = [None for _ in range(MAX_CHAR)]
# function to insert a string in trie
def insert(root: Trie, string: str, index: int) -> None:
node = root
for i in range(len(string)):
# taking ascii value to find index of
# child node
ind = ord(string[i]) - ord('a')
# making a 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 string) and store
# index of 'str' in index[]
(node.index).append(index)
# function for preorder traversal of trie
def preorder(node: Trie, arr: List[str]) -> None:
# if node is empty
if (node == None):
return
for i in range(MAX_CHAR):
if (node.child[i] != None):
# if leaf node then print all the strings
# for (node.child[i].index).size() > 0)
for j in range(len(node.child[i].index)):
print(arr[node.child[i].index[j]], end = " ")
preorder(node.child[i], arr)
# function to sort an array
# of strings using Trie
def printSorted(arr: List[str], n: int) -> None:
root = Trie()
# insert all strings of dictionary into trie
for i in range(n):
insert(root, arr[i], i)
# print strings in lexicographic order
preorder(root, arr)
# Driver program to test above
if __name__ == "__main__":
arr = ["abc", "xyz", "abcd", "bcd", "abc"]
n = len(arr)
printSorted(arr, n)
# This code is contributed by sanjeev2552
Javascript
<script>
// JavaScript implementation
// to sort an array of
// strings using Trie
let rootNode=null;
// function to insert
// a string in trie
function insert(key,index)
{
// making a new path
// if not already
if (rootNode == null)
{
rootNode = new Node();
}
let currentNode = rootNode;
for (let i = 0;i < key.length;i++)
{
let keyChar = key[i];
if (currentNode.getChild(keyChar) == null)
{
currentNode.addChild(keyChar);
}
// go to next node
currentNode = currentNode.getChild(keyChar);
}
// Mark leaf (end of string)
// and store index of 'str'
// in index[]
currentNode.addIndex(index);
}
// function for preorder
// traversal of trie
function traversePreorder(array)
{
_traversePreorder(rootNode, array);
}
function _traversePreorder(node,array)
{
if (node == null)
{
return;
}
if (node.getIndices().length > 0)
{
for (let index=0;index<
node.getIndices().length;index++)
{
document.write(array[node.getIndices()[index]] + " ");
}
}
for (let index = 'a'.charCodeAt(0);index <=
'z'.charCodeAt(0);index++)
{
_traversePreorder(node.getChild(String.fromCharCode(index)),
array);
}
}
class Node
{
constructor()
{
this.children = new Array(26);
this.indices = [];
}
getChild(index)
{
if (index < 'a' || index > 'z')
{
return null;
}
return this.children[index.charCodeAt(0) -
'a'.charCodeAt(0)];
}
addChild(index)
{
if (index < 'a' || index > 'z')
{
return;
}
let node = new Node();
this.children[index.charCodeAt(0) -
'a'.charCodeAt(0)] = node;
}
getIndices()
{
return this.indices;
}
addIndex(index)
{
this.indices.push(index);
}
}
// function to sort an array
// of strings using Trie
function printInSortedOrder(array)
{
for (let i = 0;i < array.length;i++)
{
insert(array[i], i);
}
traversePreorder(array);
}
// Driver program
array=["abc", "xyz","abcd", "bcd", "abc"];
printInSortedOrder(array);
// This code is contributed by rag2127
</script>
Producción:
abc abc abcd bcd xyz
Complejidad de tiempo: el peor de los casos ocurre cuando cada string comienza con un carácter diferente. En ese caso, visitará todos los Nodes de cada carácter de cada string. Entonces, la complejidad temporal en el peor de los casos será la suma de la longitud de cada string, es decir, O(|S1| + |S2| + |S3| + … + |Sn|) donde |S| es la longitud de la string.
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA