Жолдың басқа сызықты бұза алатынын тексеріңіз Leetcode шешімі


Күрделілік дәрежесі орта
төзімділік Ашкөздік Сұрыптау String

Проблемалық мәлімдеме

Бұл мәселеде бізге екі беріледі жолдар s1 және s2 өлшемдері бірдей. S1 жолының кейбір ауыстырулары s2 жолының кейбір ауыстыруларын бұза алатынын немесе керісінше тексеріңіз. Басқаша айтқанда, s2 s1-ді бұзуы мүмкін немесе керісінше.

0 мен n-1 аралығындағы барлық i үшін x [i]> = y [i] (алфавиттік тәртіппен) болса, x жолы y жолын (n өлшемі де) бұза алады.

мысал

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

Түсіндіру:

“Ayx” - s2 = ”xya” пермутациясы, ол “abc” жолына ауыса алады, бұл s1 = ”abc” пермутациясы.

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

Түсіндіру:

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 шешімі

Егер біз барлық символдар үшін s1-ді s2-ден артық ете алсақ, онда біз шындыққа ораламыз. Екінші жағдайда, егер біз s2 -ді s1-ден үлкен ете алсақ, онда біз де шындыққа ораламыз. Әйтпесе ешкім басқаны сындыра алмайды.

Алгоритм:

  • Егер s1 ұзындығы s2 ұзындығына тең болмаса, онда жалған мәнін қайтарыңыз.
  • Екі жолды да өсу немесе кему ретімен сұрыптаңыз.
  • S1 символдарының бойымен цикл жүргізіңіз. S1 [i]> = s2 [i] болса, әр таңбаны тексеріңіз. Егер барлық таңбалар осы шартты қанағаттандырса, онда шындық мәніне оралыңыз.
  • Енді s2 символдарының бойымен цикл жүргізіңіз. S2 [i]> = s1 [i] болса, әр таңбаны тексеріңіз. Егер барлық таңбалар осы шартты қанағаттандырса, онда шындық мәніне оралыңыз.
  • Басқа өтірік қайтару.

Іске асыру

C ++ бағдарламасы жолдың басқа кодтық шешімін бұза алатынын тексеруге арналған бағдарлама

#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 бағдарламасы

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

Жолдың басқа сызық кодын бұза алатынын тексеру үшін күрделіліктің талдауы

Уақыттың күрделілігі

O (nlog (n)): Мұндағы n - берілген жолдың ұзындығы. Біз берілген жіпті сұрыптап, екі рет сызықтық жүрдік. Демек, уақыттың күрделілігі nlogn болады.

Ғарыштың күрделілігі 

O (1): біз қосымша жад қолданған жоқпыз. Кейбір алгоритмдер үшін кеңістіктің күрделілігі O (1) -дан үлкен болуы мүмкін.