వరుసలో ఒకే పదాలను తొలగించండి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది ఫాక్ట్‌సెట్
అర్రే సార్టింగ్ స్టాక్ స్ట్రింగ్

సమస్యల నివేదిక

“వరుసగా ఒకే పదాలను ఒక క్రమంలో తొలగించు” అనే సమస్య మీకు ఇవ్వబడింది జాబితా యొక్క n తీగలను. వరుసగా రెండు ఒకే పదాలు ఉంటే, రెండింటినీ తొలగించండి. అలాంటి అన్ని జతలను తొలగించిన తర్వాత జాబితాలో మిగిలి ఉన్న మొత్తం పదాలు / తీగలను ముద్రించండి.

వరుసలో ఒకే పదాలను తొలగించండి

ఉదాహరణ

s[ ] = {ab, aa, aa, bcd, ab}
3
s[ ] = {cpp, cpp, java}
1

స్టాక్ ఉపయోగించి

అల్గారిథం

  1. యొక్క జాబితాను ప్రారంభించండి n తీగలను.
  2. ఒక సృష్టించు స్టాక్ డేటా నిర్మాణం.
  3. జాబితా యొక్క 0 నుండి పరిమాణం వరకు ప్రయాణించండి - 1.
    1. స్టాక్ ఖాళీగా ఉందో లేదో తనిఖీ చేయండి అంటే స్టాక్ పరిమాణం 0
      1. స్టాక్‌లోని జాబితాలోని ప్రస్తుత సూచిక వద్ద పదాన్ని నెట్టండి / చొప్పించండి.
    2. లేకపోతే స్ట్రింగ్ వేరియబుల్ సృష్టించి, దానిలోని స్టాక్ పైభాగంలో స్ట్రింగ్‌ను నిల్వ చేయండి.
      1. స్ట్రింగ్ వేరియబుల్‌ను జాబితాలోని ప్రస్తుత సూచిక వద్ద ఉన్న పదంతో పోల్చండి, రెండు తీగలను ఒకేలా ఉంటే.
        1. స్టాక్ ఎగువ నుండి స్ట్రింగ్ తొలగించండి.
      2. తీగలు భిన్నంగా ఉంటే.
        1. ప్రస్తుత సూచిక వద్ద స్ట్రింగ్‌ను స్టాక్‌కు నెట్టండి.
  4. స్టాక్ పరిమాణాన్ని తిరిగి ఇవ్వండి.

కోడ్

వరుసగా ఒకే పదాలను ఒక క్రమంలో తొలగించడానికి C ++ ప్రోగ్రామ్

#include<bits/stdc++.h> 
using namespace std; 
  
int removeConsSame(vector<string > s){ 
    stack<string> st; 
  
    for(int i=0; i<s.size(); i++){ 
        if(st.empty()){ 
            st.push(s[i]);
        }
        
        else{ 
            string str = st.top(); 
  
            if(str.compare(s[i]) == 0){ 
                st.pop(); 
            }
  
            else{
                st.push(s[i]);
            }
        } 
    } 
  
    return st.size(); 
} 
  
int main(){ 
    vector<string> s = {"ab", "aa", "aa", "bcd", "ab"};
    
    cout << removeConsSame(s); 
    
    return 0; 
}
3

వరుస పదాలను వరుసగా తొలగించడానికి జావా ప్రోగ్రామ్

import java.util.Vector; 
import java.util.Stack; 
  
class removeSame{ 
    
    static int removeConsSame(Vector <String > s){ 
        Stack<String> st = new Stack<>(); 
       
        for(int i=0; i<s.size(); i++){ 
            if(st.empty()){ 
                st.push(s.get(i));
            }
            
            else{ 
                String str = st.peek(); 
       
                if(str.equals(s.get(i))){     
                    st.pop(); 
                }
       
                else{
                    st.push(s.get(i));
                }
            } 
        } 
        return st.size(); 
    } 
      
    public static void main(String[] args){ 
        Vector<String> s = new Vector<>(); 
  
        s.addElement("ab"); 
        s.addElement("aa"); 
        s.addElement("aa");
        s.addElement("bcd");
        s.addElement("ab");
  
        System.out.println(removeConsSame(s)); 
    } 
}
3

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై) ఇక్కడ n అనేది జాబితాలోని తీగల సంఖ్య. మేము ఇప్పుడే తీగలను దాటినందున, సమయ సంక్లిష్టత కేవలం O (n), ఇది అల్గోరిథం సరళ సమయంలో నడుస్తుంది. గమనించదగ్గ విషయం ఏమిటంటే, తీగలను పోల్చారు మరియు తీగలకు కొంత స్థిరమైన పొడవు N కంటే తక్కువగా ఉందని మేము భావించాము. ఎందుకంటే చెత్త సందర్భంలో స్ట్రింగ్ పోలిక O (పొడవు) సమయం పడుతుంది.

అంతరిక్ష సంక్లిష్టత

పై) ఎందుకంటే మేము n తీగలను నిల్వ చేయడానికి స్థలాన్ని ఉపయోగించాము. ప్రస్తుత సూచిక వద్ద స్ట్రింగ్ మరియు స్టాక్ ఎగువన ఉన్న స్ట్రింగ్ ఒకేలా ఉండనప్పుడు. మేము ప్రస్తుత సూచిక వద్ద స్ట్రింగ్‌ను స్టాక్‌లోకి నెట్టివేస్తాము. చెత్త సందర్భంలో, మేము అన్ని తీగలను స్టాక్‌లోకి నెట్టవచ్చు. ఈ దృష్టాంతంలో O (n) స్థల సంక్లిష్టత ఏర్పడుతుంది.

స్టాక్ ఉపయోగించకుండా

అల్గారిథం

  1. యొక్క జాబితాను ప్రారంభించండి n తీగలను.
  2. జాబితా యొక్క 0 నుండి పరిమాణం వరకు ప్రయాణించండి - 2.
    1. జాబితాలోని ప్రస్తుత సూచిక వద్ద ఉన్న పదాన్ని జాబితాలోని ప్రస్తుత సూచిక + 1 వద్ద ఉన్న పదంతో పోల్చండి.
      1. రెండు తీగలను భిన్నంగా ఉంటే.
        1. ప్రస్తుత సూచికను పెంచండి
      2. రెండు తీగలను ఒకేలా ఉంటే.
        1. జాబితా నుండి రెండు తీగలను తొలగించండి / తొలగించండి.
        2. ప్రస్తుత సూచిక 0 కన్నా ఎక్కువగా ఉందో లేదో తనిఖీ చేయండి
          1. ప్రస్తుత సూచికను తగ్గించండి.
        3. జాబితా యొక్క పరిమాణాన్ని జాబితా పరిమాణంగా నవీకరించండి - 2.
  3. జాబితా పరిమాణాన్ని తిరిగి ఇవ్వండి.

కోడ్

వరుసగా ఒకే పదాలను ఒక క్రమంలో తొలగించడానికి C ++ ప్రోగ్రామ్

#include<bits/stdc++.h> 
using namespace std; 
  
int removeConsSame(vector <string > s){ 
    int n = s.size(); 
  
    for(int i=0; i<n-1; ){ 
        if(s[i].compare(s[i+1]) == 0){ 
            s.erase(s.begin()+i); 
            s.erase(s.begin()+i); 
  
            if(i > 0){ 
                i--; 
            }
  
            n = n-2; 
        } 
  
        else{
            i++;
        }
    } 
    return s.size(); 
} 
  
int main(){ 
    vector<string> s = {"ab", "aa", "aa", "bcd", "ab"};
    
    cout << removeConsSame(s); 
    
    return 0; 
}
3

వరుస పదాలను వరుసగా తొలగించడానికి జావా ప్రోగ్రామ్

import java.util.Vector; 
  
class removeSame{ 
    
    static int removeConsSame(Vector <String > s){ 
        int n = s.size(); 
       
        for(int i=0; i<n-1; ){ 
            if(s.get(i).equals(s.get(i+1))){ 
                s.remove(i); 
                s.remove(i); 
       
                if(i > 0){ 
                    i--; 
                }
       
                n = n-2; 
            } 
       
            else{
                i++;
            }
        } 
        return s.size(); 
    } 
      
    public static void main(String[] args){ 
        Vector<String> s = new Vector<>(); 
  
        s.addElement("ab"); 
        s.addElement("aa"); 
        s.addElement("aa");
        s.addElement("bcd");
        s.addElement("ab");
  
        System.out.println(removeConsSame(s)); 
    } 
}
3

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (n ^ 2) ఇక్కడ n అనేది జాబితాలోని తీగల సంఖ్య. మేము వెక్టర్ నుండి తీగలను తొలగిస్తున్నాము కాబట్టి. వెక్టర్ నుండి ఏదైనా మూలకాన్ని తొలగించడం సరళ సమయం పడుతుంది. ఎందుకంటే ఈ ఆపరేషన్ N సార్లు చేయవచ్చు. సమయం సంక్లిష్టత బహుపది.

అంతరిక్ష సంక్లిష్టత

O (1) ఎందుకంటే సమాచారాన్ని నిల్వ చేయడానికి మేము ఏ ఇంటర్మీడియట్ డేటా నిర్మాణాన్ని ఉపయోగించలేదు. తీగలను నిల్వ చేయడానికి మాత్రమే స్థలం అవసరం, ఇది ఇన్‌పుట్‌లో భాగం మరియు అల్గోరిథం కోసం స్థల సంక్లిష్టతను లెక్కించడంలో పరిగణించబడదు. కానీ ప్రోగ్రామ్ మొత్తం O (N) స్థలాన్ని తీసుకుంటుంది.