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: YesInput: 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:
- 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.
- 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 Listclass 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 subsequencebool 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 Codeint 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 approachimport 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 Listclass Node: def __init__(self, data): self.data = data; self.next = None;# Function to check if the linked list contains# a String as a subsequencedef 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 Codeif __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 approachusing 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
