Check if a string is present in the given Linked List as a subsequence
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 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)
Contact Us