શબ્દમાળા લીટકોડ સોલ્યુશનને ફરીથી ફોર્મેટ કરો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે માઈક્રોસોફ્ટ
શબ્દમાળા

સમસ્યા નિવેદન

આ સમસ્યામાં, અમને મૂળાક્ષરો આપવામાં આવે છે શબ્દમાળા એટલે કે શબ્દમાળામાં ફક્ત નાના અક્ષરો (એઝ) અને અંકો (0-9) છે. અમારે આ શબ્દમાળાના કોઈપણ ક્રમચયને પરત કરવાની જરૂર છે, જેમાં તેમાં સતત કોઈ મૂળાક્ષરો નથી અથવા કોઈ સળંગ અંકો નથી. જો આવું ના હોય ક્રમચય ત્યાં છે, પછી આપણે ખાલી શબ્દમાળા પાછા આપવાના છે.

ઉદાહરણ

s = "a0b1c2"
"0a1b2c"

સમજૂતી:

"0a1 બી 2 સી" માં કોઈ બે અડીને અક્ષરો સમાન પ્રકારનાં નથી.
"A0b1c2", "0a1b2c", "0c2a1b" પણ માન્ય અનુમતિ છે.

s = "leetcode"
""

સમજૂતી:

"લેટકોડ" માં ફક્ત અક્ષરો છે તેથી અમે તેમને અંકોથી અલગ કરી શકતા નથી.

અભિગમ

ચાલો પહેલા તે સ્થિતિ સમજીએ કે જેમાં આપણે ક્રમચય પાછા આપી શકીએ.
માની લો કે જો શબ્દમાળા "એબીસીડે" છે, તો અમે તેમાંથી કોઈ સંભવિત ક્રમચય કરી શકતા નથી જેમાં કોઈ બે મૂળાક્ષરો અથવા સંખ્યા સતત ન હોય.
તેવી જ રીતે જો શબ્દમાળા "12335" છે, તો પછી આપણે કંઈ પણ કરી શકતા નથી.
તેથી, વૈકલ્પિક આલ્ફાન્યુમેરિક શબ્દમાળાઓ બનાવવા માટે, આપણી પાસે સમાન સંખ્યાઓ અને મૂળાક્ષરો હોવા જોઈએ?
ના, ચાલો ઉદાહરણ જોઈએ "covid2019" અમારી પાસે 5 મૂળાક્ષરો અને 4 અંકો છે.
હજી પણ અમારી પાસે શક્ય જવાબો છે જેમ કે "c2o0v1i9d".

શબ્દમાળા લીટકોડ સોલ્યુશનને ફરીથી ફોર્મેટ કરો

હવે જો આ જ શબ્દમાળામાં હજી એક વધુ મૂળાક્ષરો હશે, તો ચાલો “covids2019” તો પછી આપણે કોઈ પણ સંભવિત આઉટપુટ બનાવી શકીએ નહીં.
આમ અહીં આપણને એક શરત મળી છે કે મૂળાક્ષરોની ગણતરી અને અંકોની ગણતરીનો તફાવત 1 કરતા વધારે ન હોવો જોઈએ.
એટલે કે એબીએસ (ગણતરી (અંક) -ગણતરી (મૂળાક્ષરો)) <= 1, અન્ય મુજબનું આઉટપુટ શક્ય નથી.

ચાલો હવે અલ્ગોરિધમનો સમજીએ,

અલ્ગોરિધમ

  1. વૈકલ્પિક આઉટપુટ બનાવવા માટે, આપણે અલગથી મૂળાક્ષરો અને અંકોનું જૂથ કરવું જોઈએ.
  2. તે પછી આપણે બંને જૂથોનું કદ ચકાસી શકીએ છીએ, જો તફાવત 1 કરતા વધી જાય તો આપણે પાછલી સ્ટ્રિંગ્સ. બાકી આપણે આગળ વધીએ.
  3. હવે આપણે બંને જૂથનું કદ ચકાસી શકીએ છીએ,
    જો જૂથનું કદ (મૂળાક્ષરોનું જૂથ) બીજા (અંકોના જૂથ) કરતા મોટું છે (તો પછી) આપણે આઉટપુટ શબ્દમાળામાં પ્રથમ સ્થાને મોટા જૂથના પાત્રને ભરીને પ્રારંભ કરવું પડશે.
    નહિંતર, કોઈપણ જૂથનું પાત્ર પ્રથમ સ્થાન લઈ શકે છે.
    અહીં આપણે આ કાર્ય માટે ફ્લેગ વેરિયેબલનો ઉપયોગ કરી રહ્યા છીએ. જે બંને જૂથ માટેનો વારો સિવાય કંઈ નથી. જો ધ્વજ સાચું છે, તો પછી આપણે આઉટપુટ શબ્દમાળામાં મૂળાક્ષરો મૂકીને આગળ વધીએ છીએ. નહિંતર, આપણે એક અંક મૂકીશું.
    દરેક ભરણ પર પણ, અમે બે જૂથો વચ્ચે વૈકલ્પિક રાખવા માટે ધ્વજ vertંધું કરીશું.
  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

સ્ટ્રિંગ લીટકોડ સોલ્યુશનને ફરીથી ફોર્મેટ કરવા માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન): કારણ કે, આપણે ઇનપુટ શબ્દમાળા પર રેખીય રીતે કામ કરી રહ્યા છીએ. તેથી, સમય જટિલતા ઓ (એન) હશે.

અવકાશ જટિલતા 

ઓ (એન): અમારે થોડા વધારાના શબ્દમાળાઓનો ઉપયોગ કરવો પડશે:

  • એ. મૂળાક્ષર જૂથ માટે
  • બી. અંકો જૂથ માટે
  • સી. આઉટપુટ માટે

આ બધાના કદમાં ઇનપુટ શબ્દમાળાઓની લંબાઈ મહત્તમ હોય છે
તેથી, અવકાશ જટિલતા પણ ઓ (એન) છે.