സ്ട്രിംഗ് ലീറ്റ്കോഡ് പരിഹാരം വീണ്ടും ഫോർമാറ്റുചെയ്യുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു മൈക്രോസോഫ്റ്റ്
സ്ട്രിംഗ്

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ‌, ഞങ്ങൾക്ക് ഒരു ആൽ‌ഫാന്യൂമെറിക് നൽകിയിരിക്കുന്നു സ്ട്രിംഗ് അതായത് സ്‌ട്രിംഗിന് ചെറിയ അക്ഷരങ്ങളും (az) അക്കങ്ങളും (0-9) മാത്രമേയുള്ളൂ. ഈ സ്ട്രിംഗിന്റെ ഏതെങ്കിലും ക്രമമാറ്റം ഞങ്ങൾ മടക്കിനൽകേണ്ടതുണ്ട്, അതിൽ തുടർച്ചയായ അക്ഷരമാലയോ തുടർച്ചയായ അക്കങ്ങളോ ഇല്ല. അങ്ങനെയൊന്നുമില്ലെങ്കിൽ പെർമാറ്റിഷൻ അവിടെ ഉണ്ടെങ്കിൽ, ഞങ്ങൾ ഒരു ശൂന്യമായ സ്ട്രിംഗ് നൽകണം.

ഉദാഹരണം

s = "a0b1c2"
"0a1b2c"

വിശദീകരണം:

“0a1b2c” ൽ അടുത്തുള്ള രണ്ട് പ്രതീകങ്ങൾക്കും സമാന തരം ഇല്ല.
“A0b1c2”, “0a1b2c”, “0c2a1b” എന്നിവയും സാധുവായ ക്രമമാറ്റങ്ങളാണ്.

s = "leetcode"
""

വിശദീകരണം:

“ലീറ്റ്കോഡിന്” പ്രതീകങ്ങൾ മാത്രമേ ഉള്ളൂ, അതിനാൽ അവയെ അക്കങ്ങളാൽ വേർതിരിക്കാനാവില്ല.

സമീപനം

നമുക്ക് ഒരു ക്രമമാറ്റം നൽകാനാകുന്ന അവസ്ഥ ആദ്യം മനസിലാക്കാം.
സ്ട്രിംഗ് “abcde” ആണെങ്കിൽ, അതിൽ നിന്ന് രണ്ട് അക്ഷരമാലകളോ അക്കങ്ങളോ തുടർച്ചയായി ഇല്ലാത്ത ഒരു ക്രമമാറ്റവും നടത്താൻ ഞങ്ങൾക്ക് കഴിയില്ല.
അതുപോലെ തന്നെ സ്ട്രിംഗ് “12335” ആണെങ്കിൽ ഞങ്ങൾക്ക് ഒന്നും ചെയ്യാൻ കഴിയില്ല.
അതിനാൽ, ഇതര ആൽ‌ഫാന്യൂമെറിക് സ്ട്രിംഗ് നിർമ്മിക്കുന്നതിന്, നമുക്ക് തുല്യമായ അക്കങ്ങളും അക്ഷരങ്ങളും ഉണ്ടോ?
ഇല്ല, നമുക്ക് ഉദാഹരണം “covid2019” നമുക്ക് 5 അക്ഷരങ്ങളും 4 അക്കങ്ങളും ഉണ്ട്.
എന്നിട്ടും നമുക്ക് സാധ്യമായ ഉത്തരം ഉണ്ട് ഉദാ. “C2o0v1i9d”.

സ്ട്രിംഗ് ലീറ്റ്കോഡ് പരിഹാരം വീണ്ടും ഫോർമാറ്റുചെയ്യുക

ഇപ്പോൾ അതേ സ്ട്രിംഗിൽ ഒരു അക്ഷരമാല കൂടി ഉണ്ടെങ്കിൽ, “covids2019” അനുവദിക്കുക, അപ്പോൾ നമുക്ക് സാധ്യമായ .ട്ട്‌പുട്ട് രൂപപ്പെടുത്താനും കഴിയില്ല.
അക്ഷരമാലകളുടെ എണ്ണവും അക്കങ്ങളുടെ എണ്ണവും 1 കവിയാൻ പാടില്ല എന്ന ഒരു വ്യവസ്ഥ ഇവിടെ നമുക്ക് ലഭിച്ചു.
അതായത് എബിഎസ് (എണ്ണം (അക്കങ്ങൾ) -ക (ണ്ട് (അക്ഷരമാല)) <= 1, മറ്റ് തിരിച്ച് output ട്ട്‌പുട്ട് സാധ്യമല്ല.

ഇപ്പോൾ അൽഗോരിതം മനസിലാക്കാം,

അൽഗോരിതം

  1. ഇതര output ട്ട്‌പുട്ട് സൃഷ്‌ടിക്കുന്നതിന്, അക്ഷരമാലകളും അക്കങ്ങളും വെവ്വേറെ ഗ്രൂപ്പുചെയ്യണം.
  2. അതിനുശേഷം നമുക്ക് രണ്ട് ഗ്രൂപ്പുകളുടെയും വലുപ്പം പരിശോധിക്കാം, വ്യത്യാസം 1 കവിയുന്നുവെങ്കിൽ ഞങ്ങൾ റിട്ടേൺ എംപ്റ്റി സ്ട്രിംഗ്. അല്ലെങ്കിൽ ഞങ്ങൾ കൂടുതൽ മുന്നോട്ട് പോകും.
  3. ഞങ്ങൾക്ക് ഇപ്പോൾ രണ്ട് ഗ്രൂപ്പുകളുടെയും വലുപ്പം പരിശോധിക്കാൻ കഴിയും,
    ഒരു ഗ്രൂപ്പിന്റെ വലുപ്പം (അക്ഷരമാലകളുടെ ഗ്രൂപ്പ്) മറ്റൊന്നിനേക്കാൾ (ഒന്നായി) വലുതാണെങ്കിൽ (അക്കങ്ങളുടെ ഗ്രൂപ്പ്), output ട്ട്‌പുട്ട് സ്‌ട്രിംഗിൽ ആദ്യം തന്നെ വലിയ ഗ്രൂപ്പിന്റെ ഒരു പ്രതീകം പൂരിപ്പിച്ചുകൊണ്ട് ആരംഭിക്കണം.
    അല്ലെങ്കിൽ, ഏതെങ്കിലും ഗ്രൂപ്പിന്റെ സ്വഭാവം ഒന്നാം സ്ഥാനത്തെത്തിയേക്കാം.
    ഇവിടെ ഞങ്ങൾ ഈ ടാസ്ക്കിനായി ഒരു ഫ്ലാഗ് വേരിയബിൾ ഉപയോഗിക്കുന്നു. ഇത് രണ്ട് ഗ്രൂപ്പിനും ഒരു വഴിത്തിരിവാണ്. ഫ്ലാഗ് ശരിയാണെങ്കിൽ, current ട്ട്‌പുട്ട് സ്‌ട്രിംഗിൽ നിലവിലെ സ്ഥലത്ത് അക്ഷരമാല നൽകി ഞങ്ങൾ കൂടുതൽ നീങ്ങുന്നു. അല്ലെങ്കിൽ, ഞങ്ങൾ ഒരു അക്കം ഇടും.
    ഓരോ ഫില്ലിലും, രണ്ട് ഗ്രൂപ്പുകൾക്കിടയിൽ ഒന്നിടവിട്ട് നിലനിർത്തുന്നതിന് ഞങ്ങൾ ഫ്ലാഗ് വിപരീതമാക്കും.
  4. അതിനാൽ, output ട്ട്‌പുട്ടിൽ പ്രതീകങ്ങൾ ഓരോന്നായി കൂട്ടിച്ചേർക്കുന്നതിനുമുമ്പ്, അക്ഷരമാല ഗ്രൂപ്പ് വലുപ്പത്തിൽ വലുതാണെങ്കിൽ ഞങ്ങളുടെ ഫ്ലാഗ് ശരിയാക്കും, അല്ലാത്തപക്ഷം ഫ്ലാഗ് തെറ്റായി തുടരും.
  5. ഇപ്പോൾ ഇത് output ട്ട്‌പുട്ട് സ്‌ട്രിംഗ് ആണ്, ഞങ്ങൾ അത് തിരികെ നൽകണം.

നടപ്പിലാക്കൽ

സ്ട്രിംഗ് ലീറ്റ്കോഡ് പരിഹാരം പരിഷ്കരിക്കുന്നതിനുള്ള സി ++ പ്രോഗ്രാം

#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): കാരണം, ഞങ്ങൾ ഇൻപുട്ട് സ്‌ട്രിംഗിൽ രേഖീയമായി പ്രവർത്തിക്കുന്നു. അതിനാൽ, സമയ സങ്കീർണ്ണത O (n) ആയിരിക്കും.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (n): ഞങ്ങൾക്ക് കുറച്ച് അധിക സ്ട്രിംഗുകൾ ഉപയോഗിക്കേണ്ടതുണ്ട്:

  • a. അക്ഷരമാല ഗ്രൂപ്പിനായി
  • b. അക്ക ഗ്രൂപ്പിനായി
  • സി. .ട്ട്‌പുട്ടിനായി

ഇവയുടെ വലുപ്പം ഇൻ‌പുട്ട് സ്‌ട്രിംഗിന്റെ ദൈർ‌ഘ്യമാണ്
അതിനാൽ, സ്ഥല സങ്കീർണ്ണതയും O (n) ആണ്.