አንድ ሕብረቁምፊ ሌላ ሕብረቁምፊ የሌትኮድ መፍትሄን መሰባበር ከቻለ ያረጋግጡ


የችግር ደረጃ መካከለኛ
ጽናት ስስታም መደርደር ሕብረቁምፊ

የችግሩ መግለጫ

በዚህ ችግር ውስጥ ሁለት ተሰጠን ሕብረቁምፊዎች ተመሳሳይ መጠን ያላቸው s1 እና s2. አንዳንድ የ ‹X1› ሰንሰለት መዘዋወር የአንዳንድ ሕብረቁምፊ s2 ን ወይም በተቃራኒው ሊያጠፋ እንደሚችል ያረጋግጡ ፡፡ በሌላ አገላለጽ s2 ን s1 ሊያፈርስ ይችላል ወይም በተቃራኒው።

አንድ ሕብረቁምፊ x ከ 0 እስከ n-1 መካከል ያለው x [i]> = y [i] (በፊደል ቅደም ተከተል) ከሆነ ሕብረቁምፊ y (ሁለቱም መጠናቸው n) መሰባበር ይችላል።

ለምሳሌ

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

ማብራሪያ:

“Ayx” የ “s2 =” xya ”ጠለፋ ሲሆን ወደ“ abc ”ሕብረቁምፊ ሊቋረጥ ይችላል ይህም የ s1 =“ abc ”ጠለፋ ነው።

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

ማብራሪያ:

ለ “s1 =” abe ”ሁሉም ጥፋቶች“ አበ ”፣“ አእብ ”፣“ ባእ ”፣“ ቤአ ”፣“ ኢአብ ”እና“ ኤባ ”እና“ sd = ”acd ”፣“ ካድ ”፣“ cda ”፣“ dac ”እና“ dca ”፡፡ ሆኖም ፣ ከ s2 እና በተቃራኒው በተቃራኒው አንዳንድ ጥሰቶችን ሊያጠፋ የሚችል ከ ‹1› ማፈንገጥ የለም ፡፡

ቀረበ

ለዚህ ችግር ቀላል አቀራረብ እያንዳንዱን የ s1 ን በእያንዳንዱ የ s2 ንዝረት መፈተሽ ከላይ ያለውን ሁኔታ የሚያረካ ጥንድ መኖር አለመኖሩን ለማወቅ ነው ፡፡ የሕብረቁምፊ መጠኑ አነስተኛ ከሆነ ይህንን ነገር ማድረግ እንችላለን ፡፡ ግን እዚህ የሕብረቁምፊው ርዝመት በጣም ትልቅ ነው ስለሆነም ሁሉንም ቅmቶች ለመፍጠር የማይቻል ነው።

ከችግር መግለጫው ጋር መሄድ አንድ ክር ሁለተኛውን ገመድ ሙሉ በሙሉ እንዲሸፍን እንፈልጋለን ፡፡ ለእያንዳንዱ ቁምፊ አቀማመጥ ፣ በአንዱ ሕብረቁምፊ ያለው ገጸ-ባህሪ በሁለተኛው ሕብረቁምፊ ካለው ቁምፊ (በፊደል ቅደም ተከተል መሠረት) የበለጠ መሆን አለበት የሚል ስሜት በመሸፈን ፡፡ ይህ በሕብረቁምፊ ውስጥ ያሉ ሁሉም ቁምፊዎች መከተል አለባቸው።
አሁን እዚህ ያለው ዋናው ምልከታ ሁሉም የሕብረቁምፊ ቁምፊዎች በመጀመሪያው ክር ውስጥ ከሁለተኛው የበለጠ እንዲሆኑ ከፈለግን በ s1 ውስጥ አነስተኛ ባህሪን በ s2 ውስጥ ካለው አነስተኛ ቁምፊ ጋር ማወዳደር አለብን ፡፡ በተመሳሳይ ትልቁ ንጥረ ነገር ከአንድ ትልቁ ጋር። አንድ ሰው ሌላውን ከጣሰ ወይም እንዳልሰበረ ለመፈተሽ ይህ የሽርሽር ሥራ በጣም የተሻለው ይሆናል ፡፡ ምሳሌ s1 = ”abc” እና s2 = “xya”። “Xya” ን ከለዩ በኋላ በእያንዳንዱ ነጥብ ከ “abc” ከፍ ያለ ይሆናል።

አንድ ሕብረቁምፊ ሌላ ሕብረቁምፊ የሌትኮድ መፍትሄን መሰባበር ከቻለ ያረጋግጡ

ለሁሉም ቁምፊዎች s1 ን ከ s2 የበለጠ ለማድረግ ከቻልን ወደ እውነት እንመለሳለን ፡፡ በሁለተኛ ደረጃ s2 ን ከ s1 የበለጠ ማድረግ ከቻልን ደግሞ ወደ እውነት እንመለሳለን ፡፡ አለበለዚያ ማንም ሌላውን ሊሰብረው አይችልም ፡፡

ስልተ ቀመር

  • የ s1 ርዝመት ከ s2 ርዝመት ጋር እኩል ካልሆነ ከዚያ ወደ ሐሰት ይመለሱ።
  • ሁለቱንም ሕብረቁምፊዎች ወደ ላይ በመውረድ ወይም በመውረድ ቅደም ተከተል ደርድር ፡፡
  • በ s1 ቁምፊዎች ላይ አንድ ዙር ያሂዱ። S1 [i]> = s2 [i] ከሆነ ለእያንዳንዱ ቁምፊ ያረጋግጡ። ሁሉም ገጸ-ባህሪያት ይህንን ሁኔታ ካሟሉ ከዚያ ወደ እውነት ይመለሳሉ ፡፡
  • አሁን በ s2 ቁምፊዎች ላይ አንድ ዙር ያሂዱ። S2 [i]> = s1 [i] ከሆነ ለእያንዳንዱ ቁምፊ ያረጋግጡ። ሁሉም ገጸ-ባህሪያት ይህንን ሁኔታ ካሟሉ ከዚያ ወደ እውነት ይመለሳሉ ፡፡
  • ሌላ ሐሰት ይመለሳል ፡፡

አፈጻጸም

የ C ++ መርሃግብር መርሃግብር አንድ ክር ሌላ ገመድ ማሰሪያ Leetcode Solution ሊፈርስ የሚችል ከሆነ

#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)): የተሰጠው ገመድ ርዝመት n ነው ፡፡ የተሰጠንን ገመድ ለይተን በመስመር ሁለት ጊዜ ተጓዝን ፡፡ ስለዚህ የጊዜ ውስብስብነት nlogn ይሆናል።

የቦታ ውስብስብነት 

ኦ (1) ምንም ተጨማሪ ማህደረ ትውስታ አልተጠቀምንም ፡፡ ምንም እንኳን ለአንዳንድ የመለየት ስልተ ቀመሮች የቦታ ውስብስብነት ከ O (1) የበለጠ ሊሆን ይችላል።