String Great Leetcode समाधान बनाउनुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ गुगल
LeetCode थाक घागो

समस्या वक्तव्य

"स्ट्रिंगलाई महान बनाउनुहोस्" समस्यामा स्ट्रिंग दिइन्छ सानो र माथिल्लो अक्षरहरू हुन्छन्। हामीले स्ट्रिंगलाई स्ट्रिंगमा मिल्दो अक्षरहरू हटाएर राम्रो बनाउनु पर्छ जुन स्ट्रिंगलाई नराम्रो बनाउँदैछ।
राम्रो स्ट्रिंग भनेको स्ट्रि is हो जुनसँग दुईवटा सम्बद्ध अक्षरहरू हुँदैन जहाँ दुबै वर्णहरू समान हुन् तर भिन्न अवस्थामा। हामी यस अपरेशनलाई कुनै पनि स times्ख्यामा स्ट्रि good राम्रो बनाउन सक्दछौं।

उदाहरणका

s = "leEeetcode"
"leetcode"

व्याख्या:

पहिलो चरणमा, हामी अनुक्रमणिका १ र २ वा २ र 1 लाई छनौट गर्न सक्दछौं, दुबैले "leEeetcode" लाई "leetcode" मा कम गर्नेछ।

"abBAcC"
""

व्याख्या:

सम्भावित परिदृश्यहरू हुन्:
String Great Leetcode समाधान बनाउनुहोस्

दृष्टिकोण

दिईएको स्ट्रिंगसँग केहि छेउछाउको चरित्र छ जुन समान छ तर विपरीत अवस्थामा। त्यसोभए हामीले के गर्नुपर्दछ जब हामी यी दुई क्यारेक्टरहरू भेट्छौं हामीले ती दुबैलाई हटाउनुपर्दछ र बाँकी स्ट्रि forको लागि प्रक्रिया दोहोर्‍याउनुपर्दछ।

यसको लागि हामी के गर्न सक्छौं त्यो यो छ कि हामी दिईएको स्ट्रिंगको पहिलो क्यारेक्टरबाट एटरेट गर्न सक्छौं र क्यारेक्टरलाई हाम्रो नतिजा स्ट्रिंगमा थप्न सक्दछौं यदि यो खराब छैन।
हालको क्यारेक्टर एपेन्ड गर्नु अघि हामीले यो अक्षरलाई रेस स्ट्रि toमा एपेन्डिंगले खराब बनाउँदछ कि भनेर जाँच गर्छौं वा रे स्ट्रिंगको अन्तिम क्यारेक्टरसँग तुलना गरेर। यदि अभिन्न भिन्नता (ASCII) ती दुई क्यारेक्टरहरू बीच 32२ बराबर हो भने यो खराब संयोजन हो अन्यथा यो राम्रो छ। यसको आधारमा हामी तलका अपरेशनहरू गर्ने छौं।

  • यदि चरित्र एपेन्डिंगले खराब गर्दैन भने हामी केवल चरित्रलाई पुन: जोड्नका लागि प्रयोग गर्दछौं।
  • अन्यथा, हामी थप्न सक्दैनौं र पुनः स्ट्रिंगको अन्तिम चरित्र हटाउनेछौं।

माथिको एल्गोरिथ्मको लागि हामी प्रयोग गर्न सक्दछौं स्ट्याक चरित्रलाई अन्तमा धकेल्न र अन्तबाट क्यारेक्टर आउट गर्ने डेटा संरचना।
C ++ मा हामी पनि प्रयोग गर्न सक्दछौं स्ट्रिंग क्लास क्यारेक्टरहरूको स्ट्याकको रूपमा र स्ट्याक क्लास जस्ता पुशब्याक () र पप_ब्याक () अपरेसनहरू प्रयोग गर्न सक्दछ।

कार्यान्वयन

C ++ कार्यक्रम स्ट्रिंगलाई उत्तम Leccode समाधान गर्नुहोस्

#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"

जटिलता विश्लेषण स्ट्रिंगलाई ग्रेट लेटकोड समाधान बनाउनुहोस्

समय जटिलता

O (n): जहाँ n इनपुट स्ट्रि ofको लम्बाई हो। किनकि हामी एकल लूपमा स्ट्रिंगको माध्यमबाट पुनरावृत्ति गर्दैछौं। यसैले समय जटिलता n को अर्डर हुनेछ।

ठाउँ जटिलता 

O (n): हामी हाम्रो अन्तिम परिणाम भण्डारण गर्न स्ट्याक प्रयोग गर्दैछौं। त्यसैले प्रयोग गरिएको ठाउँ एन को अर्डर हुनेछ, अर्थात O (n)।