Проверите да ли низ може прекинути неко друго решење са низом кода


Ниво тешкоће Средњи
издржљивост Похлепан сортирање низ

Изјава о проблему

У овом проблему су нам дата два струне с1 и с2 исте величине. Проверите да ли нека пермутација низа с1 може прекинути неку пермутацију низа с2 или обрнуто. Другим речима, с2 може прекинути с1 или обрнуто.

Низ к може да прекине низ и (оба величине н) ако је к [и]> = и [и] (по абецедном реду) за све и између 0 и н-1.

Пример

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

objašnjenje:

„Аик“ је пермутација с2 = „киа“ која се може разбити у низ „абц“ што је пермутација с1 = „абц“.

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

objašnjenje:

Све пермутације за с1 = "абе" су: "абе", "аеб", "бае", "беа", "еаб" и "еба", а све пермутације за с2 = "ацд" су: "ацд", "адц ”,„ Цад ”,„ цда ”,„ дац ”и„ дца ”. Међутим, не постоји ниједна пермутација из с1 која може разбити неку пермутацију из с2 и обрнуто.

Приступ

Једноставан приступ овом проблему је провера сваке пермутације с1 са сваком пермутацијом с2 да би се пронашло да ли постоји неки пар који задовољава горњи услов. То можемо учинити ако је величина низа мала. Али овде је дужина низа врло велика, па је немогуће створити све пермутације.

Ако кренемо са исказом проблема, желимо да један низ у потпуности покрије други низ. Покривајући у смислу да за сваку позицију знака, знак у једном низу треба да буде већи од једнаког знаку у другом низу (према абецедном редоследу). Ово би требало да прате сви знакови у низу.
Сада је главно запажање да ли желимо да сви знаковни знакови у првом низу буду већи од другог, онда морамо упоредити мањи знак у с1 са мањим знаком у с2. Слично већи елемент са већим. Ова пермутација ће бити оптимална за проверу да ли неко ломи другу или не. Пример с1 = ”абц” и с2 = ”киа”. Након сортирања „киа“ биће више од „абц“ у свакој тачки.

Проверите да ли низ може прекинути неко друго решење са низом кода

Ако успемо да с1 учинимо већим од с2 за све знакове, враћамо тачно. У другом случају, ако смо успели да с2 направимо већим од с1, такође враћамо истину. Иначе нико не може сломити другог.

Алгоритам:

  • Ако дужина с1 није једнака дужини с2, онда вратите фалсе.
  • Поредајте оба низа у растућем или опадајућем редоследу.
  • Покрените петљу дуж знакова с1. Проверите за сваки знак да ли је с1 [и]> = с2 [и]. Ако сви знакови задовољавају овај услов, вратите тачно.
  • Сада покрените петљу дуж знакова с2. Проверите за сваки знак да ли је с2 [и]> = с1 [и]. Ако сви знакови задовољавају овај услов, вратите тачно.
  • Иначе се враћа лажно.

Имплементација

Ц ++ програм за проверу да ли низ може да прекине неко друго решење са низом кода

#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

Анализа сложености за проверу да ли низ може прекинути неко друго решење са низом кода

Сложеност времена

О (нлог (н)): где је н дужина датог низа. Сортирали смо дати низ и прешли га два пута линеарно. Отуда ће временска сложеност бити нлогн.

Сложеност простора 

О (1): нисмо користили додатну меморију. Иако за неке алгоритме за сортирање сложеност простора може бити већа од О (1).