קוק אויב אַ שטריקל קענען ברעכן אן אנדער סטרינג לעעטקאָדע לייזונג


שוועריקייט לעוועל מיטל
ענדעראַנס זשעדנע סאָרטינג שטריקל

פּראָבלעם סטאַטעמענט

אין דעם פּראָבלעם מיר זענען געגעבן צוויי סטרינגס ס 1 און ס 2 מיט די זעלבע גרייס. קוק אויב עטלעכע פּערמיוטיישאַן פון שטריקל ס 1 קענען ברעכן עטלעכע פּערמיוטיישאַן פון שטריקל ס 2 אָדער וויצע-ווערסאַ. אין אנדערע ווערטער, s2 קענען ברעכן s1 אָדער וויצע-ווערסאַ.

א שטריקל x קען ברעכן שטריקל y (ביידע פון ​​גרייס n) אויב x [i]> = y [i] (אין אלף-בית) פאר אלע i צווישן 0 און n-1.

בייַשפּיל

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

דערקלערונג:

"ייקס" איז אַ פּערמיוטיישאַן פון ס 2 = "קסיאַ" וואָס קענען ברעכן צו שטריקל "אַבק" וואָס איז אַ פּערמיוטיישאַן פון ס 1 = "אַבק".

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

דערקלערונג:

כל פּערמיוטיישאַנז פֿאַר s1 = "abe" זענען: "abe", "aeb", "bae", "bea", "eab" און "eba" און אַלע פּערמיוטיישאַן פֿאַר s2 = "acd" זענען: "acd", "adc "," Cad "," cda "," dac "און" dca ". אָבער, עס איז נישט קיין פּערמיוטיישאַן פון s1 וואָס קענען ברעכן עטלעכע פּערמיוטיישאַן פון s2 און וויצע ווערסאַ.

צוגאַנג

א פּשוט צוגאַנג צו דעם פּראָבלעם איז צו קאָנטראָלירן יעדער פּערמיוטיישאַן פון ס 1 מיט יעדער פּערמיוטיישאַן פון ס 2 צו געפֿינען אויב זיי עקסיסטירן קיין פּאָר אַז באַפרידיקן אויבן צושטאַנד. מיר קענען טאָן דעם זאַך אויב די גרייס פון דעם שטריקל איז קליין. אָבער די לענג פון די שטריקל איז זייער גרויס, אַזוי עס איז אוממעגלעך צו מאַכן אַלע פּערמיוטיישאַנז.

מיט די פּראָבלעם ויסזאָגונג, מיר וועלן איין שטריקל צו גאָר דעקן די רגע שטריקל. אין דעם זינען אַז דער כאַראַקטער אין איין שטריקל זאָל זיין גרעסער ווי גלייַך צו כאַראַקטער אין די רגע שטריקל פֿאַר יעדער כאַראַקטער שטעלע (לויט די אַלפאַבעטאַקאַל סדר). אַלע די אותיות אין שטריקל זאָל זיין נאכגעגאנגען.
איצט די הויפּט אָבסערוואַציע איז אויב מיר וועלן אַלע די שטריקל אותיות צו זיין גרעסער אין דער ערשטער שטריקל ווי רגע, מיר מוזן פאַרגלייכן קלענערער כאַראַקטער אין ס 1 מיט קלענערער כאַראַקטער אין ס 2. סימילאַרלי גרעסער עלעמענט מיט גרעסערע. די פּערמיוטיישאַן איז אָפּטימום צו קאָנטראָלירן צי איינער ברייקס אנדערן אָדער נישט. בייַשפּיל ס 1 = "אַבק" און ס 2 = "קסיאַ". נאָך סאָרטינג "קסיאַ" עס וועט זיין העכער ווי "אַבק" אין יעדער פונט.

קוק אויב אַ שטריקל קענען ברעכן אן אנדער סטרינג לעעטקאָדע לייזונג

אויב מיר קענען מאַכן s1 גרעסער ווי s2 פֿאַר אַלע אותיות, מיר קערן אמת. אין רגע פאַל, אויב מיר קענען מאַכן ס 2 גרעסער ווי ס 1, מיר אויך קערן אמת. אַנדערש קיין איינער קענען ברעכן אנדערע.

אַלגערידאַם:

  • אויב די לענג פון s1 איז נישט גלייַך צו די לענג פון s2, קערט פאַלש צוריק.
  • סאָרט ביידע די שטריקל אין אַסענדינג אָדער אַראָפּגיין סדר.
  • לויפן אַ שלייף צוזאמען די אותיות פון ס 1. טשעק פֿאַר יעדער כאַראַקטער אויב s1 [i]> = s2 [i]. אויב אַלע די אותיות באַפרידיקן דעם צושטאַנד, קערט עס אמת.
  • איצט לויפן אַ שלייף צוזאמען די אותיות פון ס 2. טשעק פֿאַר יעדער כאַראַקטער אויב 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

Java פּראָגראַם פֿאַר טשעק אויב אַ שטריקל קענען ברעכן אן אנדער סטרינג לעעטקאָדע סאַלושאַן

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)): ווו n איז די לענג פון די געגעבן שטריקל. מיר האָבן אויסגעשטעלט די געגעבן שטריקל און דורכגעקאָכט צוויי מאָל לינעאַרלי. דערפאר די צייט קאַמפּלעקסיטי איז נלאָגן.

ספעיס קאַמפּלעקסיטי 

אָ (1): מיר האָבן נישט געוויינט קיין עקסטרע זכּרון. כאָטש פֿאַר עטלעכע סאָרטינג אַלגערידאַמז, די פּלאַץ קאַמפּלעקסיטי קענען זיין גרעסער ווי אָ (1).