Dadas dos strings en forma de listas enlazadas, la tarea es verificar si una string es el anagrama de la otra. Escriba Sí si lo son, de lo contrario escriba No.
Ejemplos:
Entrada:
Lista enlazada 1 = T->R->I->A->N->G->L->E->NULL
Lista enlazada 2 = I->N->T->E->G-> R->A->L->NULL
Salida: Sí
Explicación: Las dos strings dadas son anagramas ya que tienen los mismos caracteres presentes en tiempos iguales.Entrada:
Lista enlazada 1 = S->I->L->E->N->T->NULL
Lista enlazada 2 = L->I->S->T->E->N->NULL
Salida: Sí
Enfoque: este problema se puede resolver ordenando las listas vinculadas y luego verificando que ambas sean idénticas o no. Si son idénticos después de clasificarlos, entonces son anagramas. De lo contrario, no lo son. Ahora siga los pasos a continuación para resolver este problema:
- Ordene ambas listas vinculadas utilizando la ordenación de burbujas.
- Ahora, recorra ambas listas vinculadas desde el principio y haga coincidir cada Node correspondiente.
- Si dos Nodes correspondientes son diferentes, imprima No y regrese.
- Imprima Sí al final después de que termine el bucle.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <iostream>
using namespace std;
// Structure for a node
struct Node {
int data;
Node* next;
} Node;
// Function to swap the nodes
struct Node* swap(struct Node* ptr1,
struct Node* ptr2)
{
struct Node* tmp = ptr2->next;
ptr2->next = ptr1;
ptr1->next = tmp;
return ptr2;
}
// Function to sort the list
void bubbleSort(struct Node*** head,
int count)
{
struct Node** h;
int i, j, swapped;
for (i = 0; i <= count; i++) {
h = *head;
swapped = 0;
for (j = 0; j < count - i - 1;
j++) {
struct Node* p1 = *h;
struct Node* p2 = p1->next;
if (p1->data > p2->data) {
// Update the link
// after swapping
*h = swap(p1, p2);
swapped = 1;
}
h = &(*h)->next;
}
// Break if the loop ended
// without any swap
if (swapped == 0)
break;
}
}
// Function to insert a struct Node
// at the end of a linked list
void insert(struct Node*** head, int data)
{
struct Node* ptr = new struct Node();
ptr->data = data;
ptr->next = NULL;
if (**head == NULL) {
**head = ptr;
}
else {
struct Node* ptr1 = **head;
while (ptr1->next != NULL) {
ptr1 = ptr1->next;
}
ptr1->next = ptr;
}
}
// Function to check if both strings
// are anagrams or not
bool checkAnagram(struct Node** head1,
struct Node** head2,
int N, int M)
{
// Sort the linked list
bubbleSort(&head1, N);
bubbleSort(&head2, M);
struct Node* ptr1 = *head1;
struct Node* ptr2 = *head2;
int flag = 0;
while (ptr1 != NULL) {
if (ptr1->data == ptr2->data) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
else {
return 0;
}
}
// If one of the linked list
// doesn't end
if (!ptr1 and !ptr2) {
return 1;
}
return 0;
}
// Function to create linked lists
// from the strings
void createLinkedList(struct Node** head1,
struct Node** head2,
string s1, string s2)
{
int N = s1.size();
int M = s2.size();
// Create linked list from the array s1
for (int i = 0; i < N; i++) {
insert(&head1, s1[i]);
}
// Create linked list from the array s2
for (int i = 0; i < M; i++) {
insert(&head2, s2[i]);
}
}
// Driver Code
int main()
{
string s1 = "TRIANGLE";
string s2 = "INTEGRAL";
int N = s1.size(), M = s2.size();
// start with empty linked list
struct Node* head1 = NULL;
struct Node* head2 = NULL;
createLinkedList(&head1, &head2, s1, s2);
if (checkAnagram(&head1, &head2, N, M))
cout << "Yes";
else
cout << "No";
return 0;
}
Yes
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por akshitsaxenaa09 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA