Check if a string is present in the given Linked List as a subsequence

0 0 4 minutes read

Given a string S of size N and a linked list, the task is to check if the linked list contains a string as a subsequence. Print Yes if it contains the subsequence otherwise print No.

Example:

Input: S = “bad”, Linked List: b -> r -> a -> d -> NULL
Output: Yes

Input: S = “bad”, Linked List: a -> p -> p -> l -> e -> NULL
Output: No

Approach: This problem can be solved using two pointers one on the string and one on the linked list. Now, follow the below steps to solve this problem:

Create variable i, and initialise it with 0. Also, create a pointer cur that points at the head of the linked list.
Now, run a while loop till i is less than N and cur is not NULL and in each iteration:
1. Check if S[i] is equal to the data in the node cur or not. If it is increment i to (i+1) and move cur to the next node.
2. If it isn’t then only move cur to the next node.
If the loop ends, then check if i became N or not. If it was, then print Yes, otherwise print No.

Below is the implementation of the above approach:

C++

// 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

// 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

Python3

# 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#

// 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

Javascript

<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>

Output

Yes

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!