Перевірте, чи може рядок розірвати інше рішення зі штрих-кодом


Рівень складності Medium
витривалість Жадібний Сортування рядок

Постановка проблеми

У цій задачі нам дано два струни 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" у кожній точці.

Перевірте, чи може рядок розірвати інше рішення зі штрих-кодом

Якщо ми можемо зробити s1 більшим за s2 для всіх символів, ми повертаємо true. У другому випадку, якщо ми можемо зробити s2 більшим за s1, тоді ми також повертаємо true. Інакше ніхто не може зламати іншого.

Алгоритм:

  • Якщо довжина s1 не дорівнює довжині s2, поверніть значення false.
  • Сортуйте обидва рядки за зростанням або за спаданням.
  • Проведіть цикл уздовж символів s1. Перевірте для кожного символу, якщо s1 [i]> = s2 [i]. Якщо всі символи задовольняють цю умову, поверніть true.
  • Тепер проведіть цикл уздовж символів s2. Перевірте для кожного символу, якщо s2 [i]> = s1 [i]. Якщо всі символи задовольняють цю умову, поверніть true.
  • В іншому випадку повернення false.

Реалізація

Програма 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 для перевірки того, чи рядок може розірвати інше рішення рядкового коду

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).