स्ट्रिंग Leetcode समाधान सुधार


कठिनाई स्तर आसान
में अक्सर पूछा माइक्रोसॉफ्ट
तार

समस्या का विवरण

इस समस्या में, हमें एक अल्फ़ान्यूमेरिक दिया जाता है स्ट्रिंग यानी स्ट्रिंग में केवल कम अक्षर (az) और अंक (0-9) होते हैं। हमें इस स्ट्रिंग के किसी भी क्रमचय को वापस करने की आवश्यकता है, जिसमें इसमें कोई वर्णमाला नहीं है या लगातार अंक नहीं हैं। यदि ऐसा नहीं है परिवर्तन वहाँ है, तो हमें एक खाली स्ट्रिंग लौटना होगा।

उदाहरण

s = "a0b1c2"
"0a1b2c"

स्पष्टीकरण:

कोई भी समीपवर्ती वर्ण "0a1b2c" में समान नहीं है।
"A0b1c2", "0a1b2c", "0c2a1b" भी मान्य क्रमपरिवर्तन हैं।

s = "leetcode"
""

स्पष्टीकरण:

"लेटकोड" में केवल वर्ण होते हैं इसलिए हम उन्हें अंकों द्वारा अलग नहीं कर सकते।

दृष्टिकोण

आइए पहले उस स्थिति को समझें जिसमें हम एक क्रमचय वापस कर सकते हैं।
मान लें कि यदि स्ट्रिंग "एबेक्यूड" है, तो हम इसमें से कोई भी संभावित अनुमति नहीं दे सकते हैं जिसमें कोई दो अक्षर या संख्या लगातार नहीं हैं।
इसी तरह अगर स्ट्रिंग “12335” है तो भी हम कुछ नहीं कर सकते।
तो, वैकल्पिक अल्फ़ान्यूमेरिक स्ट्रिंग बनाने के लिए, क्या हमारे पास अंकों और अल्फाबेट्स के बराबर संख्या होनी चाहिए?
नहीं, चलो उदाहरण देखते हैं "covid2019" हमारे पास 5 अक्षर और 4 अंक हैं।
फिर भी हमारे पास ans संभव है "c2o0v1i9d"।

स्ट्रिंग Leetcode समाधान सुधार

अब अगर एक ही स्ट्रिंग में एक और वर्णमाला होगी, तो "covids2019" को छोड़ दें, फिर भी हम किसी भी संभावित आउटपुट को नहीं बना सकते हैं।
इस प्रकार यहां हमें एक शर्त मिली है कि अक्षर की संख्या और अंकों की गिनती का अंतर 1 से अधिक नहीं होना चाहिए।
एब्स (गिनती (अंक)) -काउंट (अक्षर)) <= 1, अन्य वार कोई आउटपुट संभव नहीं है।

आइए अब एल्गोरिथ्म को समझते हैं,

कलन विधि

  1. वैकल्पिक आउटपुट बनाने के लिए, हमें अलग से अक्षर और अंकों को समूहीकृत करना चाहिए।
  2. उसके बाद हम दोनों समूहों के आकार की जांच कर सकते हैं, यदि अंतर 1 से अधिक है तो हम स्ट्रिंग को वापस करते हैं। और हम आगे जाते हैं।
  3. अब हम दोनों समूह का आकार देख सकते हैं,
    यदि किसी समूह (अक्षर का समूह) का आकार (एक के बाद एक) दूसरे (अंकों के समूह) से बड़ा है, तो हमें आउटपुट स्ट्रिंग में पहले स्थान पर बड़े समूह के चरित्र को भरकर शुरू करना होगा।
    अन्यथा, किसी भी समूह का चरित्र पहले स्थान पर हो सकता है।
    यहां हम इस कार्य के लिए एक ध्वज चर का उपयोग कर रहे हैं। जो दोनों समूह के लिए एक मोड़ के अलावा कुछ नहीं है। यदि ध्वज सत्य है, तो हम आउटपुट स्ट्रिंग में वर्तमान स्थान पर वर्णमाला डालकर आगे बढ़ते हैं। अन्यथा, हम एक अंक डालेंगे।
    प्रत्येक भरण पर, हम दोनों समूहों के बीच वैकल्पिक रखने के लिए ध्वज को उल्टा करेंगे।
  4. इसलिए, इससे पहले कि हम वर्णों को एक-एक करके आउटपुट में जोड़ते हैं, हम अपने झंडे को सही रखेंगे यदि वर्णमाला समूह आकार में बड़ा है, तो दूसरा ध्वज झूठा रहेगा।
  5. अब यह आउटपुट स्ट्रिंग है और हमें इसे वापस करना होगा।

कार्यान्वयन

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

#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

सुधार के लिए जटिलता विश्लेषण स्ट्रिंग Leetcode समाधान

समय जटिलता

पर) : क्योंकि, हम इनपुट स्ट्रिंग पर रैखिक रूप से काम कर रहे हैं। इसलिए, समय जटिलता O (n) होगी।

अंतरिक्ष जटिलता 

पर) : हमें कुछ अतिरिक्त तारों का उपयोग करना होगा:

  • ए। वर्णमाला समूह के लिए
  • बी अंकों के समूह के लिए
  • सी। आउटपुट के लिए

इन सभी का आकार इनपुट स्ट्रिंग की अधिकतम लंबाई पर है
इसलिए, अंतरिक्ष जटिलता भी हे (एन) है।