சரம் சிறந்த லீட்கோட் தீர்வை உருவாக்குங்கள்  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது கூகிள்
குறியீட்டு பேட்டி நேர்காணல் தயாரிப்பு லீட்கோட் LeetCodeSolutions ஸ்டேக் சரம்

சிக்கல் அறிக்கை  

“சரம் சிறந்ததாக்கு” ​​சிக்கலில் ஒரு சரம் கொடுக்கப்பட்டிருப்பது சிறிய மற்றும் மேல் எழுத்துக்களைக் கொண்டுள்ளது. சரம் மோசமானதாக இருக்கும் சரத்தில் உள்ள எழுத்துக்களை அகற்றுவதன் மூலம் இந்த சரத்தை நல்லதாக்க வேண்டும்.
ஒரு நல்ல சரம் என்பது இரண்டு எழுத்துக்கள் ஒரே மாதிரியாக ஆனால் வேறுபட்ட வழக்கில் இரண்டு அருகிலுள்ள எழுத்துக்கள் இல்லாத ஒரு சரம். சரம் நன்றாக இருக்க எத்தனை முறை வேண்டுமானாலும் செய்யலாம்.

உதாரணமாக

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"

சரம் சிறந்த லீட்கோட் தீர்வை உருவாக்குவதற்கான சிக்கலான பகுப்பாய்வு  

நேர சிக்கலானது

ஓ (ந): N என்பது உள்ளீட்டு சரத்தின் நீளம். ஏனென்றால் நாம் ஒரு வளையத்தில் சரம் வழியாக மீண்டும் வருகிறோம். எனவே நேர சிக்கலானது n இன் வரிசையாக இருக்கும்.

விண்வெளி சிக்கலானது 

ஓ (ந): எங்கள் இறுதி முடிவைச் சேமிக்க ஒரு அடுக்கைப் பயன்படுத்துகிறோம். எனவே பயன்படுத்தப்படும் இடம் n, அதாவது O (n) வரிசையாக இருக்கும்.