स्ट्रिंग ग्रेट लीटकोड सोल्यूशन बनवा


अडचण पातळी सोपे
वारंवार विचारले Google
लेटकोड स्टॅक अक्षरमाळा

समस्या विधान

“स्ट्रिंग ग्रेट” करा या समस्येमध्ये लोअर आणि अप्पर केस अक्षरे असतात. आपल्याला स्ट्रिंग खराब करणार्‍या स्ट्रिंगमधील जवळची अक्षरे काढून ही स्ट्रिंग चांगली बनवावी लागेल.
चांगली स्ट्रिंग ही एक स्ट्रिंग असते ज्यामध्ये दोन संलग्न अक्षरे नसतात जिथे दोन्ही वर्ण एकसारखे असतात परंतु भिन्न केसची असतात. स्ट्रिंग चांगली करण्यासाठी आम्ही हे ऑपरेशन बर्‍याच वेळा करू शकतो.

उदाहरण

s = "leEeetcode"
"leetcode"

स्पष्टीकरण:

पहिल्या चरणात, आम्ही अनुक्रमणिका 1 आणि 2 किंवा 2 आणि 3 निवडू शकतो, दोन्ही "लीटकोड" ते "लीटकोड" कमी करेल.

"abBAcC"
""

स्पष्टीकरण:

संभाव्य परिस्थिती अशीः
स्ट्रिंग ग्रेट लीटकोड सोल्यूशन बनवा

दृष्टीकोन

दिलेल्या स्ट्रिंगचे काही जवळील वर्ण आहेत जे समान आहेत परंतु उलट प्रकरणात. म्हणून जेव्हा आपल्याला या दोन वर्णांचा सामना करावा लागतो तेव्हा आपण त्या दोघांना काढून टाकले पाहिजे आणि उर्वरित स्ट्रिंगसाठी पुन्हा प्रक्रिया पुन्हा करा.

त्यासाठी आपण काय करू शकतो ते म्हणजे आम्ही दिलेल्या स्ट्रिंगच्या पहिल्या कॅरेक्टरपासून पुनरावृत्ती करू आणि कॅरेक्टरला आपल्या रिजल्ट स्ट्रिंगमध्ये जोडू शकत नाही तोपर्यंत हे वाईट नाही.
सध्याचे अक्षर जोडण्यापूर्वी आम्ही हे तपासले की रेस स्ट्रिंगमध्ये हे अक्षर जोडल्यास ते खराब होईल की नाही आणि रे स्ट्रिंगच्या शेवटच्या अक्षराशी तुलना केली जाईल. अविभाज्य फरक असल्यास (एएससीआयआय) त्या दोन वर्णांमधील 32 च्या बरोबरीने ते चांगले संयोजन आहे अन्यथा ते चांगले आहे. त्या आधारे आम्ही पुढील ऑपरेशन करू:

  • जर वर्ण जोडणे खराब होणार नाही तर आम्ही फक्त त्या वर्णात आराम घालू.
  • अन्यथा, आम्ही रेसिंग स्ट्रिंगचे शेवटचे पात्र जोडू आणि काढून टाकणार नाही.

वरील अल्गोरिदमसाठी आम्ही वापरू शकतो स्टॅक अक्षराला शेवटपर्यंत ढकलणे आणि शेवटपासून अक्षर काढणे यासाठी डेटा स्ट्रक्चर.
सी ++ मध्ये आम्ही वापरू शकतो स्ट्रिंग क्लास वर्णांचा स्टॅक म्हणून आणि स्टॅक क्लास सारखी पुश_बॅक () आणि पॉपबॅक () ऑपरेशन्स वापरू शकतात.

अंमलबजावणी

मेक स्ट्रिंग ग्रेट लीटकोड सोल्यूशनसाठी सी ++ प्रोग्राम

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

string makeGood(string s) {

    string goodString;

    for(char ch:s)
    {
        if((!goodString.empty()) && abs(goodString.back()-ch)==32)  
            goodString.pop_back();
        else  
            goodString.push_back(ch);
    }

    return goodString;
}

int main() 
{
    string s = "leEeetcode";
    
    cout<<makeGood(s)<<endl;

  return 0; 
}
"leetcode"

मेक द स्ट्रिंग ग्रेट लीटकोड सोल्यूशनसाठी जावा प्रोग्राम

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

class Rextester
{  
    public static String makeGood(String s) {

        Stack<Character> stack= new Stack<Character>();

        for(int i=0;i<s.length();i++)
        {
            if((!stack.isEmpty()) && Math.abs(stack.peek()-s.charAt(i))==32 )
                stack.pop();
            else
                stack.push(s.charAt(i));
        }

        char res[]= new char[stack.size()];
        
        for(int i=res.length-1;i>=0;i--) 
            res[i]= stack.pop();

        return new String(res);

    }
    
    public static void main(String args[])
    {
        String s = "leEeetcode";

        System.out.println(makeGood(s));
        
    }
}
"leetcode"

स्ट्रिंग ग्रेट लीटकोड सोल्यूशनसाठी कॉम्प्लेक्सिटी विश्लेषण

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

ओ (एन): जेथे एन ही इनपुट स्ट्रिंगची लांबी आहे. कारण आपण एकाच लूपमध्ये स्ट्रिंगद्वारे पुनरावृत्ती करत आहोत. म्हणून वेळ जटिलता एन ऑर्डर असेल.

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

ओ (एन): आम्ही आमचा अंतिम निकाल संग्रहित करण्यासाठी स्टॅक वापरत आहोत. म्हणून वापरलेली जागा एनची क्रमवारी असेल, म्हणजेच ओ (एन).