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

두 개의 문자열이 주어졌고 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를 반환합니다.

예

으아아아

출력

으아아아

시간 복잡도 - 문자의 빈도를 계산하므로 O(N)입니다.

공간 복잡성 - 배열에 문자의 빈도를 저장하기 때문에 O(26)입니다.

한 문자열의 모든 문자가 다른 문자열보다 클 수 있도록 두 문자열의 순열이 있는지 확인하는 방법을 배웠습니다. 첫 번째 방법은 정렬 방법을 사용하고 두 번째 방법은 문자의 누적 빈도를 사용합니다.

위 내용은 주어진 문자열의 순열이 다른 주어진 문자열보다 사전순으로 큰지 확인합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!