Encuentre la última URL única de una larga lista de URL en un solo recorrido

Dada una lista muy larga de URL, averigüe la última URL única. Solo se permite un recorrido de todas las URL.

Ejemplos:

Input:
https://www.geeksforgeeks.org
https://www.geeksforgeeks.org/quiz-corner-gq/ 
http://qa.geeksforgeeks.org 
https://practice.geeksforgeeks.org 
https://ide.geeksforgeeks.org
https://write.geeksforgeeks.org  
https://www.geeksforgeeks.org/quiz-corner-gq/ 
https://practice.geeksforgeeks.org 
https://ide.geeksforgeeks.org 
https://www.geeksforgeeks.org/quiz-corner-gq/ 
http://qa.geeksforgeeks.org 
https://practice.geeksforgeeks.org

Output:
https://write.geeksforgeeks.org

Podemos resolver este problema en un recorrido utilizando Triecon una Lista Doblemente Vinculada (Podemos insertar y borrar en tiempo O(1)). La idea es insertar todas las URL en Trie una por una y verificar si está duplicada o no. Para saber si nos hemos encontrado previamente con la URL, debemos marcar el último Node de cada URL como Node hoja. Si encontramos una URL por primera vez, la insertamos en la lista doblemente vinculada y mantenemos un puntero a ese Node en la lista vinculada en el Node hoja del trie. Si encontramos una URL que ya está en el trie y tiene un puntero a la url en la lista vinculada, eliminamos el Node de la lista vinculada y establecemos su puntero en el trie en nulo. Una vez procesadas todas las URL, la lista vinculada solo contendrá las URL distintas y el Node al principio de la lista vinculada será la última URL única.

// C++ program to print distinct URLs using Trie
// and Doubly Linked List
#include <bits/stdc++.h>
using namespace std;
  
// Alphabet size (# of symbols)
const int ALPHABET_SIZE = 256;
  
// A linked list node
struct DLLNode
{
    string data;
    DLLNode* next, * prev;
};
  
// trie node
struct TrieNode
{
    TrieNode* children[ALPHABET_SIZE];
  
    // isLeaf is true if the node represents
    // end of a word
    bool isLeaf;
  
    DLLNode* LLptr;
};
  
/* Given a reference (pointer to pointer) to the
   head of a list and an int, inserts a new node
   on the front of the list. */
void push(DLLNode*& head_ref, string new_data)
{
    DLLNode* new_node = new DLLNode;
  
    // put in the data
    new_node->data = new_data;
  
    // Make next of new node as head and previous
    // as NULL
    new_node->next = (head_ref);
    new_node->prev = NULL;
  
    // change prev of head node to new node
    if(head_ref != NULL)
        head_ref->prev = new_node;
  
    // move the head to point to the new node
    head_ref = new_node;
}
  
/* Function to delete a node in a Doubly Linked List.
   head_ref --> pointer to head node pointer.
   del  -->  pointer to node to be deleted. */
void deleteNode(DLLNode*& head_ref, DLLNode* del)
{
    // base case
    if (head_ref == NULL || del == NULL)
        return;
  
    // If node to be deleted is head node
    if (head_ref == del)
        head_ref = del->next;
  
    // Change next only if node to be deleted is
    // NOT the last node
    if (del->next != NULL)
        del->next->prev = del->prev;
  
    // Change prev only if node to be deleted is
    // NOT the first node
    if (del->prev != NULL)
        del->prev->next = del->next;
  
    // Finally, free the memory occupied by del
    delete(del);
    return;
}
  
// Returns new trie node (initialized to NULLs)
TrieNode* getNewTrieNode(void)
{
    TrieNode* pNode = new TrieNode;
  
    if (pNode)
    {
        pNode->isLeaf = false;
  
        for (int i = 0; i < ALPHABET_SIZE; i++)
            pNode->children[i] = NULL;
  
        pNode->LLptr = NULL;
    }
  
    return pNode;
}
  
// If not present, inserts key into trie
// If the key is prefix of trie node, just marks leaf node
void insert(TrieNode* root, string key, DLLNode*& head)
{
    int index;
    TrieNode* pCrawl = root;
  
    for (int level = 0; level < key.length(); level++)
    {
        index = int(key[level]);
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNewTrieNode();
  
        pCrawl = pCrawl->children[index];
    }
  
    if (pCrawl->isLeaf)
    {
        // cout << "Duplicate Found " << key << endl;
        // delete from linked list
        if (pCrawl->LLptr)
            deleteNode(head, pCrawl->LLptr);
        pCrawl->LLptr = NULL;
    }
    else
    {
        // mark last node as leaf
        pCrawl->isLeaf = true;
  
        // insert to linked list
        push(head, key);
        pCrawl->LLptr = head;
    }
}
  
// Driver function
int main()
{
    string urls[] = {
        "https://www.geeksforgeeks.org",
        "https://write.geeksforgeeks.org",
        "http://quiz.geeksforgeeks.org",
        "http://qa.geeksforgeeks.org",
        "https://practice.geeksforgeeks.org",
        "https://ide.geeksforgeeks.org",
        "http://quiz.geeksforgeeks.org",
        "https://practice.geeksforgeeks.org",
        "https://ide.geeksforgeeks.org",
        "http://quiz.geeksforgeeks.org",
        "http://qa.geeksforgeeks.org",
        "https://practice.geeksforgeeks.org"
        };
  
    TrieNode* root = getNewTrieNode();
  
    // Start with the empty list
    DLLNode* head = NULL;
    int n = sizeof(urls)/sizeof(urls[0]);
  
    // Construct Trie from given URLs
    for (int i = 0; i < n; i++)
        insert(root, urls[i], head);
  
    // head of linked list will point to last
    // distinct URL
    cout << head->data << endl;
  
    return 0;
}

Producción:

https://write.geeksforgeeks.org

Este artículo es una contribución de Aditya Goel . 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.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *