주어진 문자열의 순열이 다른 주어진 문자열보다 사전순으로 큰지 확인합니다.-C++-php.cn

주어진 문자열의 순열이 다른 주어진 문자열보다 사전순으로 큰지 확인합니다.

王林

풀어 주다： 2023-09-22 08:41:13

앞으로

1159명이 탐색했습니다.

주어진 문자열의 순열이 다른 주어진 문자열보다 사전순으로 큰지 확인합니다.

두 개의 문자열이 주어졌고 i번째 인덱스에서 한 순열이 다른 순열보다 더 큰 문자를 가질 수 있도록 주어진 문자열의 순열이 존재하는지 확인해야 합니다.

문자열을 정렬하고 문자열의 각 문자를 하나씩 비교하여 문제를 해결할 수 있습니다. 또는 두 문자열의 문자 빈도를 사용하여 문제를 해결할 수 있습니다.

문제 설명 - 길이가 N인 문자열 str1과 str2가 제공됩니다. 하나가 사전순으로 다른 것보다 큰 문자열 순열이 있는지 확인해야 합니다. 이는 모든 순열이 다른 문자열 순열의 i 번째 인덱스에 있는 문자보다 큰 i 번째 인덱스의 문자를 가져야 함을 의미합니다.

예

Input - str1 = "aef"; str2 = "fgh";

출력–예

설명 – 'fgh'는 이미 'aef'보다 큽니다. 여기서, a > f, g > e, h > f.

Input – str1 = "adsm"; str2 = "obpc";

출력–아니요

설명 – 한 문자열의 모든 문자가 다른 문자열보다 큰 순열을 찾을 수 없습니다.

방법 1

이 방법에서는 두 개의 문자열을 사전순으로 정렬합니다. 그런 다음 문자열의 각 문자를 비교합니다. str1의 모든 문자가 str2보다 작거나 str2의 모든 문자가 str1보다 작은 경우 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

알고리즘

문자열을 정렬하려면 sort() 메서드를 사용하세요.
isStr1Greater 부울 변수를 정의하고 true로 초기화하세요.
문자열을 탐색하고 str1의 i번째 인덱스 위치에 있는 문자가 str2보다 작으면 isStr1Greater 값을 false로 업데이트하고 break 키워드를 사용하여 루프를 중단합니다
isStr1Greater가 true이면 루프가 성공적으로 완료되고 true를 반환합니다.
이제 문자열을 반복하여 str2가 str1보다 큰지 확인하세요. str1의 문자가 str2보다 크다면 false가 반환됩니다.
루프가 성공적으로 완료되면 true를 반환합니다.

예

으아아아

출력

으아아아

시간 복잡도 - O(N*logN) 왜냐하면 문자열을 정렬하기 때문입니다.

공간 복잡성 - 문자열을 정렬하려면 O(N)이 필요합니다.

방법 2

이 방법에서는 두 문자열 모두에 각 문자의 총 빈도를 저장합니다. 그런 다음 누적 빈도를 사용하여 하나가 다른 것보다 큰 문자열 순열을 찾을 수 있는지 결정합니다.

알고리즘

길이가 26인 map1 및 map2 배열을 정의하고 0으로 초기화합니다.
str1의 문자 빈도를 map1에 저장하고, str2의 문자 빈도를 map2에 저장합니다.
isStr1 및 isStr2 부울 변수를 정의하고 false로 초기화하여 str1이 str2보다 큰지 추적합니다.
문자열 문자의 누적 빈도를 저장하려면 cnt1 및 cnt2 변수를 정의하세요.
지도1과 지도2를 횡단하세요. cnt1에 map1[i]를 추가하고 cnt2에 map2[i]를 추가합니다.
cnt1이 cnt2보다 크면 str1부터 i번째 인덱스까지 문자의 누적 빈도가 더 큽니다. 그렇다면 str2가 이미 더 크면 false를 반환합니다. 그렇지 않으면 isStr1을 true
cnt2가 cnt1보다 크면 str2의 i번째 인덱스에 있는 문자의 누적 빈도가 더 큽니다. 그렇다면 str1이 이미 더 크면 false를 반환합니다. 그렇지 않으면 isStr2를 true
마침내 true를 반환합니다.