Сап дагы бир сапты буза ала тургандыгын текшериңиз Leetcode Solution


Кыйынчылык деңгээли орто
чыдамкайлык ач көз сорттоо аркан

Маселени билдирүү

Бул маселеде бизге экөө берилет саптар бирдей өлчөмдөгү s1 жана s2. S1 саптын кандайдыр бир алмаштырылышы s2 саптын айрым алмаштырылышын бузушу мүмкүнбү же тескерисинче. Башка сөз менен айтканда, s2 s1ди бузушу мүмкүн же тескерисинче.

Эгерде x [i]> = y [i] (алфавиттик тартипте) болсо, 0ден n-1ге чейинки бардык i үчүн, x сабы y сабын буза алат (экөө тең n өлчөмдө).

мисал

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

Explanation:

"Ayx" - s2 = "xya" орун алмашуусу, ал "abc" сабына үзүлүп кетиши мүмкүн, бул s1 = "abc" пермутациясы.

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

Explanation:

S1 = "abe" үчүн бардык орун алмашуулар: "abe", "aeb", "bae", "bea", "eab" жана "eba" жана s2 = "acd" үчүн бардык орун алмашуулар: "acd", "adc" ”,“ Cad ”,“ cda ”,“ dac ”жана“ dca ”. Бирок, s1ден кандайдыр бир орун алмаштыруучу нерсе жок, ал s2ден жана ал эми тескерисинче бир аз алмаштыра алат.

жакындоо

Бул көйгөйгө жөнөкөй ыкма - s1дин ар бир орун алмашуусун s2дин ар бир алмашуусу менен текшерип, алардын жогорудагы шартты канааттандырган кандайдыр бир түгөйүн табуу. Бул нерсени кылдын көлөмү кичине болсо жасай алабыз. Бирок бул жерде кылдын узундугу өтө чоң болгондуктан, бардык орун алмаштырууларды жаратууга мүмкүн эмес.

Көйгөйлөрдү чечүү менен бир сап экинчи сапты толугу менен камтыйт. Ар бир тамга позициясы үчүн бир саптагы белги экинчи саптагы символдон чоңураак (алфавиттик тартипке ылайык) болушу керек деген мааниде. Андан кийин саптагы бардык белгилер жазылышы керек.
Эми бул жердеги негизги байкоо, эгерде биз бардык сап белгилеринин биринчи сапта экинчисине караганда чоң болушун кааласак, анда s1деги кичине белгилер менен s2деги кичинекей белгилерди салыштыруу керек. Ушундай эле чоң элемент менен чоң элемент. Бул орун алмаштыруу бири-бирин сындырып же сындырбай тургандыгын текшерүү үчүн оптималдуу болот. Мисал s1 = "abc" жана s2 = "xya". "Xya" сорттолгондон кийин, ар бир чекитте "abc" ден жогору болот.

Сап дагы бир сапты буза ала тургандыгын текшериңиз Leetcode Solution

Эгерде биз бардык белгилер үчүн s1ди s2ден чоңураак кыла алсак, анда биз чыныгыга кайтып келебиз. Экинчи учурда, эгерде биз s2ди s1ден чоңураак кыла алсак, анда биз дагы чындыкка айланабыз. Болбосо эч ким башкасын сындыра албайт.

алгоритми:

  • Эгерде 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 - берилген саптын узундугу. Берилген жипти иреттеп, эки жолу сызык аркылуу өттүк. Демек, убакыттын татаалдыгы nlogn болот.

Космостун татаалдыгы 

O (1): биз эч кандай ашыкча эстутум колдонгон жокпуз. Айрым алгоритмдерди бөлүү үчүн мейкиндиктин татаалдыгы O (1) жогору болушу мүмкүн.