Bir simli başqa bir simli Leetcode həllini qıra biləcəyini yoxlayın

Çətinlik səviyyəsi Mühit
alqoritmlər kodlaşdırma dözümlülük Görməmiş müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions çeşidləyici SimBaxılıb 18

Problem bəyanat

Bu problemdə bizə ikisi verilir strings eyni ölçülü s1 və s2. S1 sətrinin bəzi permütasiyasının s2 sətrinin və ya əksinə bir sıra permütasiyasını qıra biləcəyini yoxlayın. Başqa sözlə, s2 s1-i qıra bilər və ya əksinə.

0 və n-1 arasındakı bütün i üçün x [i]> = y [i] (əlifba sırası ilə) olduqda x sətri y sətrini (hər ikisi də n ölçülü) qıra bilər.

misal

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

Explanation:

“Ayx” s2 = ”abc” permütasiyası olan “abc” sətirinə keçə bilən s1 = ”xya” permutasiyadır.

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

Explanation:

S1 = "abe" üçün bütün permutasiyalar bunlardır: "abe", "aeb", "bae", "bea", "eab" və "eba" və s2 = "acd" üçün bütün permütasiyalar: "acd", "adc" ”,“ Cad ”,“ cda ”,“ dac ”və“ dca ”. Bununla birlikdə, s1-dən s2-dən və əksinə, bəzi permütasiyanı qıra biləcək hər hansı bir permütasiya yoxdur.

Yanaşma

Bu problemə sadə bir yanaşma, hər bir s1 permütasiyasını s2-nin hər bir permütasiyası ilə yoxlamaqdır ki, onların yuxarıdakı şərti təmin edən hər hansı bir cüt mövcuddur. Sətrin ölçüsü kiçikdirsə, bunu edə bilərik. Ancaq burada simli uzunluq çox böyük olduğundan bütün permütasiyaları yaratmaq mümkün deyil.

Problem ifadəsi ilə davam edərək bir simlin ikinci simli tamamilə örtməsini istəyirik. Hər bir simvol mövqeyi üçün bir simldəki simvolun ikinci simldəki simvoldan (əlifba sırasına görə) daha böyük olması mənasını əhatə edir. Bunu simvoldakı bütün simvollar izləməlidir.
İndi burada əsas müşahidə bütün sətir simvollarının birinci sətirdə ikincidən daha böyük olmasını istəyiriksə, s1-dəki kiçik simi ilə s2-dəki kiçik səciyyəni müqayisə etməliyik. Eyni şəkildə daha böyük bir element daha böyükdür. Bu yer dəyişdirmə, birinin digərini qırıb pozmadığını yoxlamaq üçün optimal olacaqdır. Nümunə s1 = "abc" və s2 = "xya". "Xya" sıralandıqdan sonra hər nöqtədə "abc" dən yüksək olacaq.

Bir simli başqa bir simli Leetcode həllini qıra biləcəyini yoxlayın

Bütün simvollar üçün s1-i s2-dən çox edə bilsək, gerçək qayıdırıq. İkinci halda, s2-ni s1-dən çox edə bilsək, o zaman da doğru oluruq. Əks halda heç kim başqasını qıra bilməz.

Alqoritm:

  • Əgər s1-in uzunluğu s2-nin uzunluğuna bərabər deyilsə, yalnış qayıdır.
  • Hər iki simli artan və ya azalan qaydada çeşidləyin.
  • S1 simvolları boyunca bir döngə aparın. S1 [i]> = s2 [i] olduqda hər bir işarəni yoxlayın. Bütün simvollar bu şərti təmin edərsə, doğru qayıdın.
  • İndi s2 simvolları boyunca bir döngə aparın. S2 [i]> = s1 [i] olduqda hər bir işarəni yoxlayın. Bütün simvollar bu şərti təmin edərsə, doğrudur.
  • Başqa bir yalan qayıt.

Həyata keçirilməsi

Bir simli başqa bir simli Leetcode həllini qıra biləcəyini yoxlamaq üçün C ++ proqramı

#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

Bir Simli Başqa Bir Simli Leetcode Çözümünü Qıra biləcəyini Yoxlamaq üçün Java Proqramı

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

Bir simli başqa bir simli Leetcode həllini qıra biləcəyini yoxlamaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (nlog (n)): burada n - verilən sətrin uzunluğu. Verilən simli sıraladıq və iki dəfə xətti keçdik. Beləliklə, zamanın mürəkkəbliyi nlogn olacaqdır.

Kosmik Mürəkkəblik 

O (1): əlavə yaddaş istifadə etmədik. Bəzi çeşidləmə alqoritmləri üçün kosmik mürəkkəblik O (1) -dən çox ola bilər.

Şərh yaz

Translate »
1