Dada una array de strings arr[] , la tarea es imprimir todas las strings únicas que están presentes en la array dada.
Ejemplos:
Entrada: arr[] = { “geeks”, “geek”, “ab”, “geek” “code”, “karega” }
Salida: geeks ab code karega
Explicación:
La frecuencia de la string “geeks” es 1.
La La frecuencia de la string «geek» es 2.
La frecuencia de la string «ab» es 1.
La frecuencia de la string «code» es 1.
La frecuencia de la string «karega» es 1.
Por lo tanto, la salida requerida es » geeks ab código karega”Entrada: arr[] = { “abcde”, “abcd”, “abcd”, “co” “”, “código” }
Salida: abcde co código
Enfoque ingenuo: el enfoque más simple para resolver este problema es recorrer la array para cada string encontrada, verificar si esa string aparece en la array restante o no. Imprima esas strings que ocurren solo una vez en la array.
Complejidad de Tiempo: O(N 2 * M), donde M es la longitud máxima de la string
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando Trie . La idea es atravesar la array y para cada i -ésima string en la array, verificar si arr[i] está presente en el Trie o no. Si es cierto, marque arr[i] como elemento de array duplicado. De lo contrario, marque arr[i] como elemento de array único e inserte arr[i] en el trie . Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos isUniq[] , para verificar si un elemento de la array es único o no .
- Cree un Trie que tenga un Node raíz, digamos root , para almacenar los caracteres de cada string presente en la array dada.
- Recorra la array usando la variable i y para cada i -ésimo elemento, verifique si arr[i] está presente en el Trie o no. SI se encuentra que es verdadero, entonces actualice isUniq[i] a falso.
- De lo contrario, actualice isUniq[i] a verdadero e inserte arr[i] en Trie.
- Finalmente, recorra la array isUniq[] usando la variable i y para cada i -ésimo elemento, verifique si isUniq[i] es verdadero o no. Si se encuentra que es cierto, imprima arr[i] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Structure of // a Trie node struct TrieNode { // Stores index // of string int idx; // Check if a character is // present in the string or not TrieNode* child[26]; // Initialize a TrieNode TrieNode() { // Idx = -1: String is not // present in TrieNode idx = -1; // Initialize all child nodes // of a TrieNode to NULL for (int i = 0; i < 26; i++) { // Update child[i] child[i] = NULL; } } }; // Function to insert a string into Trie void Insert(TrieNode* root, string str, int i) { // Stores length of the string int N = str.length(); // Traverse the string str for (int i = 0; i < N; i++) { // If str[i] not present in // a Trie at current index if (!root->child[str[i] - 'a']) { // Create a new node of Trie. root->child[str[i] - 'a'] = new TrieNode(); } // Update root root = root->child[str[i] - 'a']; } // Store index of str // in the TrieNode root->idx = i; } // Function to check if string str present // in the Trie or not int SearchString(TrieNode* root, string str) { // Stores length of // the string int N = str.length(); // Traverse the string for (int i = 0; i < N; i++) { // If a character not present // in Trie at current index if (!root->child[str[i] - 'a']) { // Return str as // unique string return -1; } // Update root root = root->child[str[i] - 'a']; } // Return index of str return root->idx; } // Utility function to find the unique // string in array of strings void UtilUniqStr(vector<string>& arr, int N) { // Stores root node of the Trie TrieNode* root = new TrieNode(); // isUniq[i]: Check if i-th string // is unique or not bool isUniq[N]; // Initialize isUniq[] to false memset(isUniq, false, sizeof(isUniq)); // Insert arr[0] into the Trie Insert(root, arr[0], 0); // Mark arr[0] as unique string isUniq[0] = true; // Traverse the given array for (int i = 1; i < N; i++) { // Stores previous 1st index // of arr[i] in the array int idx = SearchString(root, arr[i]); // If arr[i] not present // in the Trie if (idx == -1) { // Mark i-th string // as unique string isUniq[i] = true; // Insert arr[i] into Trie Insert(root, arr[i], i); } // If arr[i] already present // in the Trie else { // Mark i-th string as // duplicate string in Trie isUniq[idx] = false; } } // Traverse the array for (int i = 0; i < N; i++) { // If i-th string is unique, // then print the string if (isUniq[i]) { cout << arr[i] << " "; } } } // Driver Code int main() { vector<string> arr = { "geeks", "for", "geek", "ab", "geek", "for", "code", "karega" }; int N = arr.size(); UtilUniqStr(arr, N); return 0; }
Java
// Java program to implement // the above approach import java.util.*; class GFG { // Structure of // a Trie node static class TrieNode { // Stores index // of String int idx; // Check if a character is // present in the String or not TrieNode []child = new TrieNode[26]; // Initialize a TrieNode TrieNode() { // Idx = -1: String is not // present in TrieNode idx = -1; // Initialize all child nodes // of a TrieNode to null for (int i = 0; i < 26; i++) { // Update child[i] child[i] = null; } } }; // Function to insert a String into Trie static void Insert(TrieNode root, String str, int i) { // Stores length of the String int N = str.length(); // Traverse the String str for (int j = 0; j < N; j++) { // If str[i] not present in // a Trie at current index if (root.child[str.charAt(j) - 'a']==null) { // Create a new node of Trie. root.child[str.charAt(j) - 'a'] = new TrieNode(); } // Update root root = root.child[str.charAt(j) - 'a']; } // Store index of str // in the TrieNode root.idx = i; } // Function to check if String str present // in the Trie or not static int SearchString(TrieNode root, String str) { // Stores length of // the String int N = str.length(); // Traverse the String for (int i = 0; i < N; i++) { // If a character not present // in Trie at current index if (root.child[str.charAt(i) - 'a'] == null) { // Return str as // unique String return -1; } // Update root root = root.child[str.charAt(i) - 'a']; } // Return index of str return root.idx; } // Utility function to find the unique // String in array of Strings static void UtilUniqStr(String[] arr, int N) { // Stores root node of the Trie TrieNode root = new TrieNode(); // isUniq[i]: Check if i-th String // is unique or not boolean []isUniq = new boolean[N]; // Insert arr[0] into the Trie Insert(root, arr[0], 0); // Mark arr[0] as unique String isUniq[0] = true; // Traverse the given array for (int i = 1; i < N; i++) { // Stores previous 1st index // of arr[i] in the array int idx = SearchString(root, arr[i]); // If arr[i] not present // in the Trie if (idx == -1) { // Mark i-th String // as unique String isUniq[i] = true; // Insert arr[i] into Trie Insert(root, arr[i], i); } // If arr[i] already present // in the Trie else { // Mark i-th String as // duplicate String in Trie isUniq[idx] = false; } } // Traverse the array for (int i = 0; i < N; i++) { // If i-th String is unique, // then print the String if (isUniq[i]) { System.out.print(arr[i]+ " "); } } } // Driver Code public static void main(String[] args) { String[] arr = { "geeks", "for", "geek", "ab", "geek", "for", "code", "karega" }; int N = arr.length; UtilUniqStr(arr, N); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach root = None # Structure of # a Trie node class TrieNode: # Stores index # of string def __init__(self): self.idx = -1 self.child = [None]*26 # Function to insert a string into Trie def Insert(str, i): global root # Stores length of the string N = len(str) root1 = root # Traverse the string str for i in range(N): # If str[i] not present in # a Trie at current index if (not root1.child[ord(str[i]) - ord('a')]): # Create a new node of Trie. root1.child[ord(str[i]) - ord('a')] = TrieNode() # Update root root1 = root1.child[ord(str[i]) - ord('a')] # Store index of str # in the TrieNode root1.idx = i return root1 # Function to check if string str present # in the Trie or not def SearchString(str): global root root1 = root # Stores length of # the N = len(str) # Traverse the for i in range(N): # If a character not present # in Trie at current index if (not root1.child[ord(str[i]) - ord('a')]): # Return str as # unique return -1 # Update root root1 = root1.child[ord(str[i]) - ord('a')] # Return index of str return root1.idx # Utility function to find the unique # string in array of strings def UtilUniqStr(arr, N): global root # Stores root node of the Trie root = TrieNode() d = {} for i in arr: d[i] = d.get(i, 0) + 1 # isUniq[i]: Check if i-th string # is unique or not isUniq = [False] * N # Initialize isUniq[] to false # memset(isUniq, false, sizeof(isUniq)); # Insert arr[0] into the Trie Insert(arr[0], 0) # Mark arr[0] as unique string isUniq[0] = True # print(root.child[6].child) # Traverse the given array for i in range(1, N): # Stores previous 1st index # of arr[i] in the array idx = SearchString(arr[i]) # If arr[i] not present # in the Trie if (idx == -1 and d[arr[i]] == 1): # Mark i-th string # as unique string isUniq[i] = True # Insert arr[i] into Trie Insert(arr[i], i) # If arr[i] already present # in the Trie else: # Mark i-th string as # duplicate string in Trie isUniq[idx] = False # Traverse the array for i in range(N): # If i-th string is unique, # then print the string if (isUniq[i]): print(arr[i], end = " ") # Driver Code if __name__ == '__main__': arr = ["geeks", "for","geek", "ab", "geek","for", "code", "karega"] N = len(arr) UtilUniqStr(arr, N) # This code is contributed by mohit kumar 29
C#
// C# program to implement // the above approach using System; class GFG { // Structure of // a Trie node class TrieNode { // Stores index // of String public int idx; // Check if a character is // present in the String or not public TrieNode []child = new TrieNode[26]; // Initialize a TrieNode public TrieNode() { // Idx = -1: String is not // present in TrieNode idx = -1; // Initialize all child nodes // of a TrieNode to null for (int i = 0; i < 26; i++) { // Update child[i] child[i] = null; } } }; // Function to insert a String into Trie static void Insert(TrieNode root, String str, int i) { // Stores length of the String int N = str.Length; // Traverse the String str for (int j = 0; j < N; j++) { // If str[i] not present in // a Trie at current index if (root.child[str[j] - 'a'] == null) { // Create a new node of Trie. root.child[str[j] - 'a'] = new TrieNode(); } // Update root root = root.child[str[j] - 'a']; } // Store index of str // in the TrieNode root.idx = i; } // Function to check if String str present // in the Trie or not static int SearchString(TrieNode root, String str) { // Stores length of // the String int N = str.Length; // Traverse the String for (int i = 0; i < N; i++) { // If a character not present // in Trie at current index if (root.child[str[i] - 'a'] == null) { // Return str as // unique String return -1; } // Update root root = root.child[str[i] - 'a']; } // Return index of str return root.idx; } // Utility function to find the unique // String in array of Strings static void UtilUniqStr(String[] arr, int N) { // Stores root node of the Trie TrieNode root = new TrieNode(); // isUniq[i]: Check if i-th String // is unique or not bool []isUniq = new bool[N]; // Insert arr[0] into the Trie Insert(root, arr[0], 0); // Mark arr[0] as unique String isUniq[0] = true; // Traverse the given array for (int i = 1; i < N; i++) { // Stores previous 1st index // of arr[i] in the array int idx = SearchString(root, arr[i]); // If arr[i] not present // in the Trie if (idx == -1) { // Mark i-th String // as unique String isUniq[i] = true; // Insert arr[i] into Trie Insert(root, arr[i], i); } // If arr[i] already present // in the Trie else { // Mark i-th String as // duplicate String in Trie isUniq[idx] = false; } } // Traverse the array for (int i = 0; i < N; i++) { // If i-th String is unique, // then print the String if (isUniq[i]) { Console.Write(arr[i] + " "); } } } // Driver Code public static void Main(String[] args) { String[] arr = { "geeks", "for", "geek", "ab", "geek", "for", "code", "karega" }; int N = arr.Length; UtilUniqStr(arr, N); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program to implement // the above approach // Structure of // a Trie node class TrieNode { constructor() { this.idx = -1; this.child = new Array(26); for (let i = 0; i < 26; i++) { // Update child[i] this.child[i] = null; } } } // Function to insert a String into Trie function Insert(root,str,i) { // Stores length of the String let N = str.length; // Traverse the String str for (let j = 0; j < N; j++) { // If str[i] not present in // a Trie at current index if (root.child[str[j].charCodeAt(0) - 'a'.charCodeAt(0)]==null) { // Create a new node of Trie. root.child[str[j].charCodeAt(0) - 'a'.charCodeAt(0)] = new TrieNode(); } // Update root root = root.child[str[j].charCodeAt(0) - 'a'.charCodeAt(0)]; } // Store index of str // in the TrieNode root.idx = i; } // Function to check if String str present // in the Trie or not function SearchString(root,str) { // Stores length of // the String let N = str.length; // Traverse the String for (let i = 0; i < N; i++) { // If a character not present // in Trie at current index if (root.child[str[i].charCodeAt(0) - 'a'.charCodeAt(0)] == null) { // Return str as // unique String return -1; } // Update root root = root.child[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]; } // Return index of str return root.idx; } // Utility function to find the unique // String in array of Strings function UtilUniqStr(arr,N) { // Stores root node of the Trie let root = new TrieNode(); // isUniq[i]: Check if i-th String // is unique or not let isUniq = new Array(N); // Insert arr[0] into the Trie Insert(root, arr[0], 0); // Mark arr[0] as unique String isUniq[0] = true; // Traverse the given array for (let i = 1; i < N; i++) { // Stores previous 1st index // of arr[i] in the array let idx = SearchString(root, arr[i]); // If arr[i] not present // in the Trie if (idx == -1) { // Mark i-th String // as unique String isUniq[i] = true; // Insert arr[i] into Trie Insert(root, arr[i], i); } // If arr[i] already present // in the Trie else { // Mark i-th String as // duplicate String in Trie isUniq[idx] = false; } } // Traverse the array for (let i = 0; i < N; i++) { // If i-th String is unique, // then print the String if (isUniq[i]) { document.write(arr[i]+ " "); } } } // Driver Code let arr=["geeks", "for", "geek", "ab", "geek", "for", "code", "karega" ]; let N = arr.length; UtilUniqStr(arr, N); // This code is contributed by patel2127 </script>
geeks ab code karega
Complejidad de Tiempo: O(N * M), donde M es la longitud máxima de la string
Espacio Auxiliar: O(N * 26)
Publicación traducida automáticamente
Artículo escrito por sourav2901 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA