एखादी स्ट्रिंग आणखी एक स्ट्रिंग लेटकोड सोल्यूशन तोडू शकते का ते तपासा


अडचण पातळी मध्यम
सहनशक्ती लोभी वर्गीकरण अक्षरमाळा

समस्या विधान

या समस्येमध्ये आम्हाला दोन दिले जातात स्ट्रिंग्स s1 आणि s2 समान आकाराचे. स्ट्रिंग एस 1 चे काही क्रम बदलणे स्ट्रिंग एस 2 किंवा त्याउलट उलटचे काही क्रम खंडित करू शकते का ते तपासा. दुसर्‍या शब्दांत एस 2 एस 1 किंवा त्याउलट तोडू शकतो.

X [i]> = y [i] (वर्णानुक्रमात) ० आणि एन -१ मधील सर्व i साठी स्ट्रिंग x स्ट्रिंग y (दोन्ही आकार n ची) खंडित करू शकते.

उदाहरण

s1 = "abc", s2 = "xya"
true

स्पष्टीकरण:

"आयएक्स" एस 2 = "एक्सआयए" चे अनुक्रम आहे जे "एबीसी" स्ट्रिंगमध्ये खंडित होऊ शकते जे एस 1 = "एबीसी" चे अनुक्रम आहे.

s1 = "abe", s2 = "acd"
false

स्पष्टीकरण:

एस 1 = "अबी" साठी सर्व परवानग्या आहेत: "अबी", "अएब", "बीए", "बीए", "ईएबी" आणि "इबा" आणि एस २ = "एसीडी" साठीचे सर्व अनुमतीः "एसीडी", "अ‍ॅडसी" ”,“ कॅड ”,“ सीडीए ”,“ डाक ”आणि“ डीसीए ”. तथापि, एस 2 कडून असे कोणतेही परमिट नाही जे एस 1 व त्याउलट काही अनुक्रमे खंडित करू शकेल.

दृष्टीकोन

या समस्येचा सोपा दृष्टिकोन म्हणजे एस 1 ची प्रत्येक क्रमवारी एस 2 च्या प्रत्येक क्रमांकासह तपासणे म्हणजे त्यांचे अस्तित्व वरील स्थितीची पूर्ती करणारी कोणतीही जोडी आहे की नाही हे शोधण्यासाठी. जर स्ट्रिंगचा आकार लहान असेल तर आपण हे करू शकतो. परंतु येथे स्ट्रिंगची लांबी खूप मोठी आहे म्हणून सर्व क्रम तयार करणे अशक्य आहे.

प्रॉब्लेम स्टेटमेंटला जाताना आम्हाला एक स्ट्रिंग हवी आहे की दुसरी स्ट्रिंग पूर्णपणे लपवावी. प्रत्येक वर्ण स्थानासाठी, एका स्ट्रिंगमधील वर्ण दुसर्‍या स्ट्रिंगमधील वर्णांपेक्षा (अक्षराच्या क्रमानुसार) मोठे असणे आवश्यक आहे. हे स्ट्रिंगमधील सर्व वर्णांद्वारे केले पाहिजे.
येथे मुख्य निरीक्षणामध्ये असे आहे की जर आपल्याला सर्व स्ट्रिंग अक्षरे पहिल्या स्ट्रिंगमध्ये सेकंदापेक्षा मोठी असतील तर आपल्याला एस 1 मधील छोट्या कॅरेक्टरची एस 2 मधील छोट्या कॅरॅक्टरशी तुलना करावी लागेल. त्याच प्रमाणे मोठ्या घटकांसह मोठा घटक. एखाद्याने दुसरा ब्रेक केला की नाही ते तपासण्यासाठी ही क्रमवारी इष्टतम असेल. S1 = "abc" आणि s2 = "xya" चे उदाहरण. “Xya” क्रमवारी लावल्यानंतर ते प्रत्येक बिंदूत “abc” पेक्षा जास्त असेल.

एखादी स्ट्रिंग आणखी एक स्ट्रिंग लेटकोड सोल्यूशन तोडू शकते का ते तपासा

जर आपण सर्व वर्णांसाठी एस 1 पेक्षा अधिक एस 2 बनविण्यास सक्षम केले तर आम्ही खरे परत येऊ. दुसर्‍या बाबतीत जर आपण एस 2 पेक्षा एस 1 बनवू शकला तर आपण सत्य देखील परत येऊ. अन्यथा कोणीही इतरांना तोडू शकत नाही.

अल्गोरिदम:

  • जर एस 1 ची लांबी एस 2 लांबीच्या बरोबरीची नसेल तर चुकीची परत जा.
  • चढत्या किंवा उतरत्या क्रमाने दोन्ही स्ट्रिंगची क्रमवारी लावा.
  • एस 1 च्या वर्णांसह लूप चालवा. S1 [i]> = s2 [i] असल्यास प्रत्येक वर्ण तपासा. जर सर्व पात्रांनी ही अट पूर्ण केली असेल तर सत्य परत येईल.
  • आता s2 च्या अक्षरासह लूप चालवा. S2 [i]> = s1 [i] असल्यास प्रत्येक वर्ण तपासा. जर सर्व पात्रांनी ही अट पूर्ण केली असेल तर सत्य परत येईल.
  • अन्यथा खोटे परत.

अंमलबजावणी

सी ++ प्रोग्राम तपासण्यासाठी जर एखादा स्ट्रिंग आणखी एक स्ट्रिंग लीटकोड सोल्यूशन तोडू शकतो

#include <bits/stdc++.h>
using namespace std;

bool checkIfCanBreak(string s1, string s2)
{
    if(s1.length() != s2.length()) return false;

    sort(s1.begin(),s1.end());
    sort(s2.begin(),s2.end());

    int i=0;
    while(s1[i])
    {
        if(s1[i]<s2[i]) break;
        i++;
    }

    if(i==s1.length()) return true;

    i=0;
    while(s2[i])
    {
        if(s1[i]>s2[i]) break;
        i++;
    }

    if(i==s2.length()) return true;

    return false;
}

int main() 
{
    string s1 = "abc";
    string s2 = "xya";
    if( checkIfCanBreak( s1, s2) )
        cout<< "true" ;
    else
        cout<< "false";
    return 0; 
}
true

एखादा स्ट्रिंग आणखी एक स्ट्रिंग लीटकोड सोल्यूशन तोडू शकतो किंवा नाही यासाठी जावा प्रोग्राम

import java.util.*;
class Rextester{
    
    public static boolean checkIfCanBreak(String s1, String s2) 
    {    
        if(s1.length() != s2.length()) return false;
        
        char[] c1=s1.toCharArray();
        char[] c2=s2.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        
        int i=0;
        while(i<s1.length())
        {
            if(c1[i]<c2[i]) break;
            i++;
        }
        
        if(i==s1.length()) return true;
        
        i=0;
        while(i<s2.length())
        {
            if(c1[i]>c2[i]) break;
            i++;
        }
        
        if(i==s2.length()) return true;
        
        return false;        
    }
    
    public static void main(String args[])
    {
        String s1 = "abc";
        String s2 = "xya";
        System.out.println(checkIfCanBreak( s1, s2) );
    }
}
true

एखाद्या स्ट्रिंगने आणखी एक स्ट्रिंग लीटकोड सोल्यूशन तोडू शकते का हे तपासण्यासाठी कॉम्प्लेक्सिटी विश्लेषण

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

ओ (नलॉग (एन)): जेथे एन दिलेली स्ट्रिंगची लांबी आहे. आम्ही दिलेली स्ट्रिंगची क्रमवारी लावली आणि दोनदा रेषेचा मागोवा घेतला. म्हणून वेळेची गुंतागुंत कोंडी होईल.

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

ओ (1): आम्ही कोणतीही अतिरिक्त मेमरी वापरली नाही. जरी काही क्रमवारी लावण्यासाठी अल्गोरिदमसाठी जागा गुंतागुंत ओ (1) पेक्षा जास्त असू शकते.