შეამოწმეთ, აქვს თუ არა სტრიქონს სხვა სტრიქონის დაშლა Leetcode Solution


Რთული ტური საშუალო
გამძლეობა ხარბ დახარისხება სიმებიანი

პრობლემის განცხადება

ამ პრობლემის დროს ორი გვეძლევა სიმები s1 და s2 იგივე ზომით. შეამოწმეთ, s1 სიმების ზოგიერთმა შეცვლამ შეიძლება დაარღვიოს სტრიქონის s2– ის ზოგიერთი შეცვლა ან პირიქით. სხვა სიტყვებით რომ ვთქვათ, s2– ს შეუძლია დაარღვიოს s1 ან პირიქით.

X სტრიქონს შეუძლია დაანგრიოს y სიმები (ორივე ზომის n), თუ x [i]> = y [i] (ანბანური თანმიმდევრობით) ყველა i- სთვის 0-დან n-1-მდე.

მაგალითი

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

განმარტება:

"Ayx" არის s2 = "xya" - ს ჩანაცვლება, რომელსაც შეუძლია გატეხოს "abc" სტრიქონი, რომელიც s1 = "abc" - ის პერმუტაციაა.

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

განმარტება:

S1 = ”abe” - ს ყველა შეცვლაა: ”abe”, ”aeb”, ”bae”, ”bea”, ”eab” და ”eba” და ყველა permutation for s2 = ”acd” არის: ”acd”, ”adc "," Cad "," cda "," dac "და" dca ". ამასთან, s1– დან არ არსებობს რაიმე ჩანაცვლება, რომელსაც შეუძლია დაანგრიოს s2– ის გარკვეული პერმუტაცია და პირიქით.

მიდგომა

ამ მიდგომის მარტივი მიდგომაა s1– ის თითოეული პერმუტაციის შემოწმება s2– ის თითოეული პერმუტაციით, თუ არსებობს მათი რაიმე წყვილი, რომლებიც აკმაყოფილებს ზემოთ მოცემულ პირობას. ამის გაკეთება შეგვიძლია, თუ სიმების ზომა მცირეა. მაგრამ აქ სიმების სიგრძე ძალიან დიდია, ამიტომ შეუძლებელია ყველა პერმუტაციის შექმნა.

პრობლემის დებულებასთან ერთად ჩვენ გვინდა, რომ ერთი სტრიქონი მთლიანად ფარავს მეორე სტრიქონს. იმის გათვალისწინებით, რომ სიმბოლოების თითოეული პოზიციისთვის სიმბოლო ერთ სტრიქონზე უნდა აღემატებოდეს სიმბოლოს მეორე სტრიქონზე (ანბანური თანმიმდევრობით). ამას უნდა მიჰყვეს სიმების სიმბოლოები.
ახლა მთავარი დაკვირვებაა აქ: თუ გვსურს რომ სიმების ყველა სიმბოლო პირველ სტრიქონში უფრო დიდი იყოს, ვიდრე მეორე, მაშინ s1- ის უფრო მცირე სიმბოლოს უნდა შევადაროთ s2- ის უფრო მცირე სიმბოლოს. ანალოგიურად უფრო დიდი ელემენტი უფრო დიდით. ეს ჩანაცვლება ოპტიმალური იქნება იმის შესამოწმებლად, არღვევს თუ არა სხვას. მაგალითი s1 = ”abc” და s2 = ”xya”. ”Xya” დახარისხების შემდეგ ის უფრო მაღალი იქნება, ვიდრე “abc” თითოეულ წერტილში.

შეამოწმეთ, აქვს თუ არა სტრიქონს სხვა სტრიქონის დაშლა Leetcode Solution

თუ ჩვენ შეგვიძლია s1 გავაკეთოთ s2– ზე მეტი ყველა სიმბოლოსთვის, მაშინ ვუბრუნდებით true- ს. მეორე შემთხვევაში, თუ ჩვენ შეგვიძლია s2 გავზარდოთ s1– ზე, ასევე ვუბრუნდებით true- ს. თორემ სხვას ვერავინ დაარღვევს.

ალგორითმი:

  • თუ s1 სიგრძე არ არის s2 სიგრძის ტოლი, მაშინ დაბრუნდი false.
  • დაალაგეთ ორივე სტრიქონი ზრდადობით ან კლებადობით.
  • გაუშვით მარყუჟი s1- ის სიმბოლოების გასწვრივ. შეამოწმეთ თითოეული სიმბოლო, თუ s1 [i]> = s2 [i]. თუ ყველა პერსონაჟი აკმაყოფილებს ამ პირობას, მაშინ დაბრუნდი ჭეშმარიტი.
  • ახლა გაუშვით ციკლი s2- ის სიმბოლოების გასწვრივ. შეამოწმეთ თითოეული სიმბოლო, თუ s2 [i]> = s1 [i]. თუ ყველა პერსონაჟი აკმაყოფილებს ამ პირობას, მაშინ დაბრუნდი ჭეშმარიტი.
  • სხვა დაბრუნების ყალბი.

განხორციელება

C ++ პროგრამა, შეამოწმეთ, აქვს თუ არა სტრიქონს სხვა სტრიქონის ამოხსნა Leetcode ამოხსნა

#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 პროგრამა შემოწმების მიზნით, აქვს თუ არა სტრიქონს სხვა სტრიქონის დაშლა Leetcode ამოხსნისთვის

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

სირთულის ანალიზი, რათა შეამოწმოს, აქვს თუ არა სტრიქონს სხვა სტრიქონის Leetcode ამოხსნის დაშლა

დროის სირთულე

O (nlog (n)): სადაც n მოცემული სტრიქონის სიგრძეა. ჩვენ დავახარისხეთ მოცემული სტრიქონი და ორჯერ გადავკვეთეთ წრფივად. ამრიგად, დროის სირთულე არ იქნება ცნობილი.

სივრცის სირთულე 

O (1): ჩვენ არ გამოვიყენეთ დამატებითი მეხსიერება. მიუხედავად იმისა, რომ ზოგიერთი დახარისხების ალგორითმისთვის სივრცის სირთულე შეიძლება იყოს მეტი ვიდრე O (1).