Праверце, ці можа радок разарваць іншае рашэнне радка Leetcode


Узровень складанасці серада
цягавітасць Прагны сартаванне Радок

Пастаноўка праблемы

У гэтай праблеме нам дадзены два радкі 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", а ўсе перастаноўкі для s2 = "acd": "acd", "adc »,« Cad »,« cda »,« dac »і« dca ». Аднак няма ніякай перастаноўкі з s1, якая можа парушыць некаторую перастаноўку з s2 і наадварот.

Падыход

Просты падыход да гэтай праблемы заключаецца ў праверцы кожнай перастаноўкі s1 з кожнай перастаноўкай s2, каб знайсці, ці існуе якая-небудзь пара, якая задавальняе вышэй умове. Мы можам зрабіць гэта, калі памер радка невялікі. Але тут даўжыня радка вельмі вялікая, таму немагчыма стварыць усе перастаноўкі.

Пераходзячы да вырашэння праблемы, мы хочам, каб адзін радок цалкам пакрываў другі радок. Пакрыццё ў сэнсе, што для кожнай пазіцыі сімвала сімвал у адным радку павінен быць большым, чым роўны знаку ў другім радку (у адпаведнасці з алфавітным парадкам). Пасля гэтага павінны ісці ўсе сімвалы ў радку.
Зараз галоўнае назіранне: калі мы хочам, каб усе сімвалы радкоў былі больш у першай радку, чым у другой, тады нам трэба параўноўваць меншы сімвал у s1 з меншым у s2. Аналагічна большы элемент з большым. Гэтая перастаноўка будзе аптымальнай для праверкі, парушае адна іншая ці не. Прыклад s1 = "abc" і s2 = "xya". Пасля сартавання "xya" ён будзе вышэй, чым "abc" у кожнай кропцы.

Праверце, ці можа радок разарваць іншае рашэнне радка Leetcode

Калі мы можам зрабіць s1 большым за s2 для ўсіх сімвалаў, мы вяртаем true. У другім выпадку, калі мы можам зрабіць s2 большым за s1, мы таксама вяртаем праўду. Інакш ніхто не можа зламаць іншага.

Алгарытм:

  • Калі даўжыня s1 не роўная даўжыні s2, вярніце false.
  • Сартаваць абедзве радкі ў парадку ўзрастання або змяншэння.
  • Правядзіце цыкл па сімвалах s1. Праверце для кожнага сімвала, калі s1 [i]> = s2 [i]. Калі ўсе сімвалы задавальняюць гэтую ўмову, вернеце true.
  • Цяпер запусціце цыкл па сімвалах s2. Праверце для кожнага сімвала, калі s2 [i]> = s1 [i]. Калі ўсе сімвалы задавальняюць гэтую ўмову, вернеце true.
  • У адваротным выпадку вяртанне ілжывае.

Рэалізацыя

Праграма 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).