문자열이 다른 문자열 Leetcode 솔루션을 깨뜨릴 수 있는지 확인


난이도 중급
지구력 탐욕스러운 정렬

문제 정책

이 문제에서 우리는 문자열 s1과 s2는 같은 크기입니다. 문자열 s1의 일부 순열이 문자열 s2의 일부 순열을 손상시킬 수 있는지 또는 그 반대인지 확인하십시오. 즉, s2는 s1을 중단하거나 그 반대로 할 수 있습니다.

0과 n-1 사이의 모든 i에 대해 x [i]> = y [i] (알파벳 순서) 인 경우 문자열 x는 문자열 y (둘 다 크기 n)를 끊을 수 있습니다.

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

설명 :

"ayx"는 s2 = "abc"의 순열 인 "abc"문자열로 나눌 수있는 s1 = "xya"의 순열입니다.

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보다 크게 만들 수 있으면 true를 반환합니다. 그렇지 않으면 아무도 다른 사람을 깰 수 없습니다.

연산:

  • s1의 길이가 s2의 길이와 같지 않으면 false를 반환합니다.
  • 두 문자열을 모두 오름차순 또는 내림차순으로 정렬합니다.
  • s1의 문자를 따라 루프를 실행합니다. s1 [i]> = s2 [i] 인 경우 각 문자를 확인합니다. 모든 문자가이 조건을 충족하면 true를 반환합니다.
  • 이제 s2의 문자를 따라 루프를 실행합니다. s2 [i]> = s1 [i] 인 경우 각 문자를 확인하십시오. 모든 문자가이 조건을 충족하면 true를 반환합니다.
  • 그렇지 않으면 false를 반환합니다.

실시

문자열이 다른 문자열 Leetcode 솔루션을 깨뜨릴 수 있는지 확인하는 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

문자열이 다른 문자열 Leetcode 솔루션을 깨뜨릴 수 있는지 확인하는 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

문자열이 다른 문자열 Leetcode 솔루션을 깨뜨릴 수 있는지 확인하기위한 복잡성 분석

시간 복잡성

O (nlog (n)) : 여기서 n은 주어진 문자열의 길이입니다. 주어진 문자열을 정렬하고 선형으로 두 번 순회했습니다. 따라서 시간 복잡도는 nlogn입니다.

공간 복잡성 

O (1) : 추가 메모리를 사용하지 않았습니다. 일부 정렬 알고리즘의 경우 공간 복잡성이 O (1)보다 클 수 있습니다.