स्ट्रिंग लीटकोड सोल्यूशनचे रीफॉर्मेट करा


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

समस्या विधान

या समस्येमध्ये, आम्हाला एक अक्षरे दिले जाते स्ट्रिंग म्हणजेच स्ट्रिंगमध्ये फक्त लोअरकेस अक्षरे (azझ) आणि अंक (0-9) आहेत. आम्हाला या स्ट्रिंगचा कोणताही क्रम बदलणे आवश्यक आहे, ज्यात त्यामध्ये सलग वर्णमाला नाही किंवा सलग अंक नाहीत. तसे नसल्यास क्रमवारी तिथे आहे तर आपल्याला रिकामी स्ट्रिंग परत करावी लागेल.

उदाहरण

s = "a0b1c2"
"0a1b2c"

स्पष्टीकरण:

“0a1b2c” मध्ये दोन जवळचे वर्ण समान प्रकारचे नाहीत.
“A0b1c2”, “0a1b2c”, “0c2a1b” देखील वैध परवानग्या आहेत.

s = "leetcode"
""

स्पष्टीकरण:

“लीटकोड” मध्ये फक्त वर्ण आहेत म्हणून आम्ही त्यांना अंकांद्वारे विभक्त करू शकत नाही.

दृष्टीकोन

प्रथम आपण क्रम बदलू शकतो त्या स्थितीस समजू.
समजा जर स्ट्रिंग “abcde” असेल तर आपण त्यापासून कोणतेही अनुक्रम बदलू शकत नाही ज्यामध्ये दोन अक्षरे किंवा संख्या सलग नसतील.
जर स्ट्रिंग जर 12335 असेल तर आपण काहीही करू शकत नाही.
तर वैकल्पिक अक्षरांक बनवण्यासाठी आपल्याकडे अंक व अक्षरे समान संख्या असावी का?
नाही, “कोविड २०१2019” चे उदाहरण पाहूया, आपल्याकडे pha अक्षरे आणि digit अंक आहेत.
तरीही आमच्याकडे उत्तरे उपलब्ध आहेत उदा. “C2o0v1i9d”.

स्ट्रिंग लीटकोड सोल्यूशनचे रीफॉर्मेट करा

आता जर त्याच स्ट्रिंगमध्ये आणखी एक अक्षरे असतील तर “covids2019” तर आपण कोणतेही संभाव्य आउटपुट तयार करू शकणार नाही.
अशा प्रकारे येथे आपल्याला अशी अट मिळाली आहे की अक्षरांची संख्या आणि अंकांची संख्या 1 पेक्षा जास्त नसावी.
म्हणजेच एबीएस (गणना (अंक) -काउंट (अक्षरे)) <= 1, इतर शहाणा कोणतेही आउटपुट शक्य नाही.

चला आता अल्गोरिदम समजून घेऊ,

अल्गोरिदम

  1. वैकल्पिक आऊटपुट तयार करण्यासाठी आपण अक्षरे व अंकांचे गटबद्ध वेगळे केले पाहिजे.
  2. त्यानंतर जर आम्ही दोन्ही गटांचा आकार तपासू शकतो, जर फरक 1 पेक्षा जास्त असेल तर आम्ही परत येऊ. नाहीतर आम्ही पुढे जाऊ.
  3. आता आपण दोन्ही गटांचे आकार तपासू शकतो.
    जर एखाद्या गटाचा आकार (अक्षराचा समूह) दुसर्‍यापेक्षा (अंकांचा समूह) मोठा असेल तर आपल्याला आउटपुट स्ट्रिंगमध्ये प्रथम स्थानावर मोठ्या गटाचे वर्ण भरुन सुरुवात करावी लागेल.
    अन्यथा, कोणत्याही गटाचे पात्र प्रथम स्थान घेऊ शकेल.
    येथे आम्ही या कार्यासाठी ध्वजांक वापरत आहोत. जे दोन्ही गटासाठी एक वळणाव्यतिरिक्त काहीही नाही. ध्वज बरोबर असल्यास आऊटपुट स्ट्रिंगमध्ये सध्याच्या ठिकाणी अक्षरे ठेवून आपण पुढे जाऊ. अन्यथा आम्ही अंक ठेवू.
    प्रत्येक भरण्यानुसार आम्ही दोन गटांमधील परस्पर बदल करण्यासाठी ध्वज उलटा करू.
  4. आऊटपुटमध्ये अक्षरे जोडण्यापूर्वी आम्ही अक्षरे समूहात जास्त असल्यास आपला ध्वज खरे ठेवू अन्यथा ध्वज असत्य राहू.
  5. आता ही आउटपुट स्ट्रिंग आहे आणि तीच आपल्याला परत करावी लागेल.

अंमलबजावणी

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

#include <iostream>
using namespace std;

string reformat(string s) {
        
        string alphas;
        string digs;
        
        for(int i=0;i<s.length();i++){
            char ch=s[i];
            string str=string(1, ch); 
            if(ch>='0' && ch<='9')digs.append(str);
            else alphas.append(str);
        }
        
        int alen=alphas.length();
        int dlen=digs.length();
        
        int diff=abs(alen-dlen);
        if(diff>1)return "";
        
        string ans;
        
        bool flag=0;
        if(alen-dlen==1)flag=1;
        
        int j=0,k=0;
        for(int i=0;i<s.length();i++){
            if(flag){
                string str=string(1, alphas[j++]); 
                ans.append(str);
            }else{
                string str=string(1, digs[k++]); 
                ans.append(str);
            }
            flag=!flag;
        }
    
        return ans;
    }


int main() {
  string str="covid2019";
  string ans=reformat(str);
    cout<<ans<<endl;	
  return 0;
}
c2o0v1i9d

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

import java.util.*;
class ReformatString{
  public static  String reformat(String s) {
        
        StringBuilder alphas=new StringBuilder();
        StringBuilder digs=new StringBuilder();
        
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch>='0' && ch<='9')digs.append(ch);
            else alphas.append(ch);
        }
        
        int alen=alphas.length();
        int dlen=digs.length();
        
        int diff=Math.abs(alen-dlen);
        if(diff>1)return "";
        
        StringBuilder ans=new StringBuilder();
        
        boolean flag=false;
        if(alen-dlen==1)flag=true;
        
        int j=0,k=0;
        for(int i=0;i<s.length();i++){
            if(flag){
                ans.append(alphas.charAt(j++));
            }else{
                ans.append(digs.charAt(k++));
            }
            flag=!flag;
        }
        return ans.toString();
    }
  
    public static void main(String args[]){
        
    String str="covid2019";
    String ans=reformat(str);
    System.out.println(ans);
    }
}
c2o0v1i9d

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

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

ओ (एन): कारण, आम्ही इनपुट स्ट्रिंगवर रेषाने कार्य करत आहोत. म्हणून, वेळ गुंतागुंत ओ (एन) असेल.

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

ओ (एन): आम्हाला काही अतिरिक्त तार वापराव्या लागतील:

  • अ. वर्णमाला गटासाठी
  • बी. अंक गटासाठी
  • सी. आउटपुट साठी

या सर्वांचा आकार इनपुट स्ट्रिंगची किमान लांबी आहे
म्हणून, अवकाश अवघडपणा देखील ओ (एन) आहे.