Verifique si una string está presente en la lista enlazada dada como una subsecuencia

Dada una string S de tamaño N y una lista enlazada , la tarea es comprobar si la lista enlazada contiene una string como subsecuencia. Imprima Sí si contiene la subsecuencia; de lo contrario, imprima No.

Ejemplo:

Entrada: S = «malo», Lista enlazada: b -> r -> a -> d -> NULL
Salida: Sí

Entrada: S = «malo», Lista enlazada: a -> p -> p -> l -> e -> NULL
Salida: No

Enfoque: este problema se puede resolver usando dos punteros, uno en la string y otro en la lista enlazada. Ahora, siga los pasos a continuación para resolver este problema:

1. Cree la variable i e inicialícela con 0. Además, cree un puntero cur que apunte al encabezado de la lista vinculada.
2. Ahora, ejecute un ciclo while hasta que i sea menor que N y cur no sea NULL y en cada iteración:
   1. Compruebe si S[i] es igual a los datos en el Node cur o no. Si lo es, incremente i a (i+1) y mueva cur al siguiente Node.
   2. Si no es así, solo mueva cur al siguiente Node.
3. Si el bucle termina, comprueba si me convertí en N o no. Si lo fue, imprima Sí , de lo contrario imprima No.

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Node of Linked List
class Node {
public:
    char data;
    Node* next;
 
    Node(char d)
    {
        data = d;
        next = NULL;
    }
};
 
// Function to check if the linked list contains
// a string as a subsequence
bool checkSub(Node* head, string S)
{
    Node* cur = head;
    int i = 0, N = S.size();
 
    while (i < N and cur) {
        if (S[i] == cur->data) {
            i += 1;
        }
        cur = cur->next;
    }
 
    if (i == N) {
        return 1;
    }
    return 0;
}
 
// Driver Code
int main()
{
    Node* head = new Node('b');
    head->next = new Node('r');
    head->next->next = new Node('a');
    head->next->next->next = new Node('d');
 
    string S = "bad";
 
    if (checkSub(head, S)) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
}

// Java code for the above approach
import java.util.*;
class GFG
{
 
  // Node of Linked List
  static class Node {
 
    char data;Node next;
 
    Node(char d)
    {
      data = d;
      next = null;
    }
 
  };
 
  // Function to check if the linked list contains
  // a String as a subsequence
  static boolean checkSub(Node head, String S)
  {
    Node cur = head;
    int i = 0, N = S.length();
 
    while (i < N && cur!=null) {
      if (S.charAt(i) == cur.data) {
        i += 1;
      }
      cur = cur.next;
    }
 
    if (i == N) {
      return true;
    }
    return false;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    Node head = new Node('b');
    head.next = new Node('r');
    head.next.next = new Node('a');
    head.next.next.next = new Node('d');
 
    String S = "bad";
 
    if (checkSub(head, S)) {
      System.out.print("Yes");
    }
    else {
      System.out.print("No");
    }
  }
}
 
// This code is contributed by gauravrajput1

# Python code for the above approach
 
# Node of Linked List
class Node:
    def __init__(self, data):
        self.data = data;
        self.next = None;
 
# Function to check if the linked list contains
# a String as a subsequence
def checkSub(head, S):
    cur = head;
    i = 0;
    N = len(S);
 
    while (i < N and cur != None):
        if (S[i] == cur.data):
            i += 1;
         
        cur = cur.next;
     
    if (i == N):
        return True;
     
    return False;
 
# Driver Code
if __name__ == '__main__':
    head =  Node('b');
    head.next =  Node('r');
    head.next.next =  Node('a');
    head.next.next.next =  Node('d');
 
    S = "bad";
 
    if (checkSub(head, S)):
        print("Yes");
    else:
        print("No");
     
 
# This code is contributed by Rajput-Ji

// C# code for the above approach
using System;
 
public class GFG
{
 
  // Node of Linked List
  class Node {
 
    public char data;
    public Node next;
 
    public Node(char d)
    {
      data = d;
      next = null;
    }
 
  };
 
  // Function to check if the linked list contains
  // a String as a subsequence
  static bool checkSub(Node head, String S)
  {
    Node cur = head;
    int i = 0, N = S.Length;
 
    while (i < N && cur!=null) {
      if (S[i] == cur.data) {
        i += 1;
      }
      cur = cur.next;
    }
 
    if (i == N) {
      return true;
    }
    return false;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    Node head = new Node('b');
    head.next = new Node('r');
    head.next.next = new Node('a');
    head.next.next.next = new Node('d');
 
    String S = "bad";
 
    if (checkSub(head, S)) {
      Console.Write("Yes");
    }    
    else {
      Console.Write("No");
    }
  }
}
 
// This code is contributed by 29AjayKumar

<script>
       // JavaScript code for the above approach
 
       // Node of Linked List
       class Node {
 
           constructor(d) {
               this.data = d;
               this.next = null;
           }
       };
 
       // Function to check if the linked list contains
       // a string as a subsequence
       function checkSub(head, S) {
           let cur = head;
           let i = 0, N = S.length;
 
           while (i < N && cur) {
               if (S[i] == cur.data) {
                   i += 1;
               }
               cur = cur.next;
           }
 
           if (i == N) {
               return 1;
           }
           return 0;
       }
 
       // Driver Code
       let head = new Node('b');
       head.next = new Node('r');
       head.next.next = new Node('a');
       head.next.next.next = new Node('d');
 
       let S = "bad";
 
       if (checkSub(head, S)) {
           document.write("Yes");
       }
       else {
           document.write("No");
       }
 
 // This code is contributed by Potta Lokesh
   </script>

Yes

Complejidad temporal: O(N)
Espacio auxiliar: O(1)