چيڪ ڪريو جيڪڏهن ڪو اسٽرنگ هڪ ٻئي اسٽرنگ ليٽ ڪوڊ جو حل ٽوڙي سگهي ٿو


تڪليف جي سطح وچولو
پورو ٿيو لالچ ترتيب ڏيڻ اسٽرنگ

مسئلي جو بيان

انهي مسئلي ۾ اسان ٻه ڏجن ٿا پودا s1 ۽ s2 ساڳئي سائيز سان. چڪاس ڪريو ته ڇا ھڪڙي اسٽرنگ ايس 1 جو ڪجھ اسٽرنگ ايس 2 جو ڪجھ وقف ٿي سگھي ٿو يا ان جي برعڪس. ٻين لفظن ۾ s2 ٽوڙي سگھي ٿو s1 يا ان جي برعڪس.

ھڪڙي اسٽرنگ x کي ٽوڙي سگھي ٿو y (ٻئي سائيز n) جيڪڏھن x [i]> = y [i] (الفابيٽ واري ترتيب ۾) سڀني لاءِ مون کي 0 ۽ n-1 جي وچ ۾.

مثال

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

وضاحت:

"آڪسڪس" s2 = "xya" جو هڪ متبادل آهي ، جيڪو “abc” واري اسٽرنگ کي ٽوڙي سگھي ٿو جيڪو s1 = ”abc” جو هڪ امتياز آهي.

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

وضاحت:

s1 = ”abe“ لاءِ سڀئي اجازتون آهن: ”abe“، “aeb”، “bae”، “bea”، “eab” and “eba” and all permutation for s2 = ”acd” are: “acd”، “adc ”،“ ڪيڊ ”،“ سي ڊي ”،“ ڊي سي ”۽“ ڊي سي ”. تنهن هوندي ، s1 مان ڪا اجازت نه آهي جيڪا s2 ۽ ڪجهه اهڙي طرح سان ڪجهه اجازت ختم ڪري سگهي ٿي.

چرچو

هن مسئلي جو هڪ سادو طريقو اهو آهي ته s1 جي هر اجازت سان s2 جي هر اجازت کي چيڪ ڪريو اهو معلوم ڪرڻ لاءِ ته ڇا انهن جو ڪو جوڙو موجود آهي جيڪي مٿي conditionاڻايل حالت کي مطمئن ڪن؟ اسان اهو ڪم ڪري سگهون ٿا جيڪڏهن تار جو اندازو نن isڙو آهي. پر هتي واري تار جو قد تمام وڏو آهي ، تنهن ڪري اهو سڀ اجازتون ٺاهڻ ناممڪن آهي.

مسئلي واري بيان سان وڃ اسان هڪ تار کي مڪمل طور تي ٻئي تار کي toڪڻ چاهيون ٿا. انهي معنى ۾ احاطه ڪرڻ ته هر ڪردار جي جڳهه لاءِ ، هڪ تار تي ڪردار ٻيو وارڊ جي برابر برابر هجڻ گهرجي (الفابيٽ جي ترتيب مطابق) اهو جملو سڀني اکرن جي پيروي ڪرڻ گهرجي.
ھاڻي بنيادي مشاهدو ھتي آھي جيڪڏھن اسان چاھيوٿا ته اھو سمورو اسٽرڪچر ھڪٻئي جي مقابلي ۾ ٻئي کان پھريون وڏو ھجي پوءِ اسان کي s1 ۾ نن characterن اکرن کي s2 ۾ نن characterن اکرن سان مقابلو ڪرڻو پوندو. ساڳيء طرح وڏو عنصر هڪ وڏي سان. اهو اجازت مناسب طور تي جانچڻ بهتر ٿيندو ته ڪو هڪ ٻئي کي ٽوڙي ٿو يا نه. مثال s1 = "abc" ۽ s2 = "xya". "xya" جي ترتيب ڏيڻ کان پوءِ اھو ھر ھڪڙي نقطي تي "abc" کان وڏو ھوندو.

چيڪ ڪريو جيڪڏهن ڪو اسٽرنگ هڪ ٻئي اسٽرنگ ليٽ ڪوڊ جو حل ٽوڙي سگهي ٿو

جيڪڏهن اسان s1 کان تمام ڪردارن لاءِ وڌيڪ کان وڌيڪ ٺاھڻ جي قابل آھيون ته پوءِ اسين سچا موٽون ٿا. ٻي صورت ۾ جيڪڏهن اسان s2 کي سئي کان وڌيڪ وڏو ڪري سگھون ٿا ته پوءِ پڻ اسان صحيح موٽون ٿا. ٻي صورت ۾ ڪوبه ٻئي کي ٽوڙي نٿو سگھي.

الگهان:

  • جيڪڏهن s1 جي ڊيگهه s2 جي ڊيگهه برابر ناهي ته غلط واپس ڪريو.
  • مٿين ٻنهي اسڪننگ کي مٿي چڙهڻ يا هيٺئين ترتيب ۾ ترتيب ڏيو.
  • S1 جي ڪردارن سان گڏ هڪ loopري هليو. هر هڪ ڪردار لاءِ جاچ ڪريو جيڪڏهن s1 [i]> = s2 [i]. جيڪڏھن سڀ اکر ھن شرط کي مطمئن ڪن ته پوءِ واپس ٿيو سچا.
  • ھاڻي هلائيندڙ ھلندڙن سان گڏ ھڪڙي لوپ ايس s2 کي. هر هڪ ڪردار لاءِ جاچ ڪريو جيڪڏهن s2 [i]> = s1 [i]. جيڪڏھن سڀ اکر ھن شرط کي مطمئن ڪن ته پوءِ واپس ٿيو سچا.
  • ايلس غلط موٽندي.

تي عملدرآمد

چيڪ ڪرڻ لاءِ C ++ پروگرام جيڪڏهن ڪو اسٽرنگ هڪ ٻئي اسٽرنگ ليٽ ڪوڊ جو حل ٽوڙي سگهي ٿو

#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

چيڪ ڪرڻ لاءِ پيچيدگي وارو تجزيو ، جيڪڏهن ڪو تار ٻيو اسٽرنگ ليٽ ڪوڊ جو حل ٽوڙي سگهي ٿو

وقت جي پيچيدگي

اي [nlog (n)): جتي ڏنل ڏني وئي جي ڊيگهه آهي. اسان ڏنل اسٽرنگ کي ترتيب ڏنو ۽ لڪير سان ٻه دفعا گذاريو. انهيء وقت جي پيچيدگي گهٽجي ويندي.

خلائي پيچيدگي 

اي (1): اسان وڌيڪ يادگيري استعمال نه ڪيو. جيتوڻيڪ ڪجھ ترتيب ڏيڻ وارا الگورتھم لاءِ جڳھ واري پيچيدگي O (1) کان وڌي سگھي ٿي.