சரம் லீட்கோட் தீர்வை மறுசீரமைக்கவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது மைக்ரோசாப்ட்
சரம்

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

இந்த சிக்கலில், எங்களுக்கு ஒரு எண்ணெழுத்து வழங்கப்படுகிறது சரம் அதாவது சரம் சிறிய எழுத்துக்கள் (அஸ்) மற்றும் இலக்கங்கள் (0-9) மட்டுமே உள்ளது. இந்த சரத்தின் எந்தவொரு வரிசைமாற்றத்தையும் நாங்கள் திருப்பித் தர வேண்டும், அதில் தொடர்ச்சியான எழுத்துக்கள் இல்லை அல்லது தொடர்ச்சியான இலக்கங்கள் இல்லை. அப்படி இல்லை என்றால் வரிசைமாற்றம் உள்ளது, பின்னர் நாம் ஒரு வெற்று சரம் திரும்ப வேண்டும்.

உதாரணமாக

s = "a0b1c2"
"0a1b2c"

விளக்கம்:

“0a1b2c” இல் இரண்டு அருகிலுள்ள எழுத்துக்கள் ஒரே வகையைக் கொண்டிருக்கவில்லை.
“A0b1c2”, “0a1b2c”, “0c2a1b” ஆகியவை செல்லுபடியாகும் வரிசைமாற்றங்கள்.

s = "leetcode"
""

விளக்கம்:

“லீட்கோடில்” எழுத்துக்கள் மட்டுமே உள்ளன, எனவே அவற்றை இலக்கங்களால் பிரிக்க முடியாது.

அணுகுமுறை

நாம் ஒரு வரிசைமாற்றத்தை திருப்பித் தரக்கூடிய நிலையை முதலில் புரிந்துகொள்வோம்.
சரம் “abcde” எனில், இரண்டு எழுத்துக்கள் அல்லது எண்கள் தொடர்ச்சியாக இல்லாத எந்தவொரு வரிசைமாற்றத்தையும் நாம் செய்ய முடியாது.
இதேபோல் சரம் “12335” என்றால் எங்களால் எதுவும் செய்ய முடியாது.
எனவே, மாற்று எண்ணெழுத்து சரம் செய்ய, நமக்கு சமமான இலக்கங்கள் மற்றும் எழுத்துக்கள் இருக்க வேண்டுமா?
இல்லை, உதாரணத்தை பார்ப்போம் “covid2019” எங்களிடம் 5 எழுத்துக்கள் மற்றும் 4 இலக்கங்கள் உள்ளன.
இன்னும் நாம் சாத்தியமான பதில்களைக் கொண்டிருக்கிறோம் எ.கா. “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

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

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

ஓ (ந): ஏனெனில், நாங்கள் உள்ளீட்டு சரத்தில் நேர்கோட்டுடன் செயல்படுகிறோம். எனவே, நேர சிக்கலானது O (n) ஆக இருக்கும்.

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

ஓ (ந): நாம் சில கூடுதல் சரங்களை பயன்படுத்த வேண்டும்:

  • a. எழுத்துக்கள் குழுவுக்கு
  • b. இலக்கக் குழுவுக்கு
  • c. வெளியீட்டிற்கு

இவை அனைத்தின் அளவும் உள்ளீட்டு சரத்தின் நீளம்
எனவே, விண்வெளி சிக்கலானது O (n) ஆகும்.