स्ट्रिंगची लिंक्ड यादी पॅलिंड्रोम तयार करते का ते तपासा


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन सफरचंद ब्लूमबर्ग कॅपिटल वन सिस्को फेसबुक Google हस्तगत करा आयएक्सएल मायक्रोसॉफ्ट न्युटॅनिक्स ओरॅकल पेटीएम Snapchat उबेर यांडेक्स
दुवा साधलेली यादी लिंक्डलिस्ट अक्षरमाळा

समस्या विधान

“स्ट्रिंग्सची दुवा साधलेली यादी पालिंड्रोम तयार करते का ते तपासा” या समस्येमध्ये आम्ही एक जोडलेली यादी स्ट्रिंग डेटा हाताळत आहे. डेटा पॅलिंड्रोम तयार करतो की नाही हे तपासण्यासाठी प्रोग्राम लिहा.

उदाहरण

ba->c->d->ca->b
1

स्पष्टीकरण: वरील उदाहरणात आपण पाहू शकतो की “बाकडॅकॅब” स्ट्रिंग एक पालिंड्रोम आहे

दृष्टीकोन

एक दुवा साधलेली सूची दिली ज्यात प्रत्येक नोडमध्ये एक स्ट्रिंग आहे. आम्हाला दुवा साधलेल्या सूचीतील डेटा पॅलिंड्रोम तयार करतो की नाही हे तपासावे लागेल. एक तार आहे पॅलिंड्रोम जर ते मागे सारखेच अग्रेषित वाचते. उदाहरणार्थ, “बाकडॅकॅब” ही संख्या एक पालिंड्रोम आहे. पुढे आणि मागे ट्रॅव्हर्स केल्यावर त्यास घटकांची समान क्रम असल्यास दुवा साधलेली सूची पॅलिंड्रोम तयार करते.

अल्गोरिदम

  1. रिक्त तार प्रारंभ करा.
  2. दुवा साधलेल्या सूचीचा आढावा घ्या आणि त्या स्ट्रिंगमध्ये लिंक केलेल्या यादीतील सर्व घटक संचयित करा.
  3. संबंधित संबंधित पहिली आणि शेवटची अक्षरे समान आहेत की नाही हे तपासण्यासाठी दुवा साधलेल्या सूचीचा आढावा घ्या. जर कधीकधी ते समान नसतील तर हे पॅलिंड्रोम तयार करणार नाही.

अंमलबजावणी

स्ट्रिंगची दुवा साधलेली यादी पालिंड्रोम तयार करते का ते तपासण्यासाठी सी ++ प्रोग्राम

#include<bits/stdc++.h>
using namespace std;

class MyLinkedList {
public:
    struct ListNode {
        ListNode *next;
        string val;
        ListNode(string a): next(NULL), val(a){}
    };
    ListNode *head;

    MyLinkedList():head(NULL) {
    }
    
    void addAtHead(string val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    bool isPlalindrome(){
    	string str = "";
    	ListNode* ptr = head;
    	while(ptr){
    		str+=ptr->val;
    		ptr = ptr->next;
    	}
    	int n = str.size();
    	for(int i=0;i<n/2;i++){
    		if(str[i]!=str[n-i-1]){
    			return false;
    		}
    	}
    	return true;
    }

    void print_list(){
    	ListNode* node = head;
    while(node){
      cout<<node->val<<" ";
      node = node->next;
    }
        cout<<endl;
  }
};

int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead("b");
  list->addAtHead("ca");
  list->addAtHead("d");
  list->addAtHead("c");
  list->addAtHead("ba");
  
  cout<<list->isPlalindrome();
}

जावा प्रोग्राम स्ट्रिंग्सची दुवा साधलेली यादी पालिंड्रोम तयार करते का ते तपासण्यासाठी

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
  
  public static void main (String[] args) throws java.lang.Exception{
    
    MyLinkedList obj = new MyLinkedList();
    obj.addAtHead("b");
    obj.addAtHead("ca");
    obj.addAtHead("d");
    obj.addAtHead("c");
    obj.addAtHead("ba");
    
    System.out.println(obj.isPalindrome());
  }
  
  public static class MyLinkedList {
    
      class Node{
          Node next = null;
          String val = "";
          
          public Node(String val){
              this.val = val;
          }
      }
      
      private Node head;
      private int size;

      public MyLinkedList() {
          this.head = null;
          this.size = 0;
      }
      
      
      public void addAtHead(String val) {
          Node node = new Node(val);
          if(this.size == 0){
              this.head = node;
          }
          else{
              node.next = this.head;
              this.head = node;
          }
          this.size++;
      }
      
    public boolean isPalindrome(){
      String str="";
      Node curr = head;
      while(curr!=null){
        str+=curr.val;
        curr = curr.next;
      }
      
      int n = str.length();
      for(int i=0;i<n/2;i++){
        if(str.charAt(i)!=str.charAt(n-i-1)){
          return false;
        }
      }
      return true;
    }

    public void printList(){
      Node curr = head;
      while(curr!=null){
        System.out.print(curr.val+" ");
        curr = curr.next;
      }
      System.out.println("");
    }
      
  }
}
1

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे n दिलेल्या लिंक केलेल्या यादीमध्ये उपस्थित नोड्सची संख्या आहे. येथे आम्ही स्ट्रिंगमध्ये सर्व व्हॅल्यूज समाविष्ट करतो आणि पॅलिंड्रोम कंडिशनसाठी त्या स्ट्रिंगची तपासणी करतो.

स्पेस कॉम्प्लेक्सिटी

O (n) कारण आम्ही दिलेल्या स्ट्रिंग यादीच्या नोडची सर्व मूल्ये एकत्रित करुन तयार केलेली स्ट्रिंग वापरतो.