A[i]는 문자열 s의 길이(i + 1) 접두사에서 고유한 문자의 수를 나타내는 n개의 숫자로 구성된 배열 A가 있다고 가정합니다. 주어진 접두사 배열을 만족하는 사전순으로 가장 작은 문자열을 찾습니다. 모든 문자는 영문 소문자[a-z]입니다. 해당 문자열이 없으면 -1을 반환합니다.
따라서 입력이 A =[1,1,2,3,4]와 같으면 접두사[0]에는 1개의 고유한 문자가 있고 접두사[1]에는 1개의 고유한 문자가 있으므로 출력은 aabcd가 됩니다. 2개의 고유한 문자가 있고, prefix[3]에는 3개의 고유한 문자가 있고, prefix[4]에는 4개의 고유한 문자가 있으며 문자열이 가장 작습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=A의 크기
-
문자 :='a'
-
문자열 :=빈 문자열
-
n <1 또는 A[0]이 1이 아니면
-
반환 -1
-
-
string :=string 연결 문자
-
문자 :=현재 문자의 다음 문자
-
범위 1에서 n까지의 i에 대해 수행
-
차이 :=A[i] - A[i - 1]
-
차이> 1 또는 차이 <0 또는 A[i]> 26이면
-
반환 -1
-
-
그렇지 않으면 차이가 0과 같을 때
-
string :=string 연결 'a'
-
-
그렇지 않으면
-
string :=string 연결 문자
-
문자 :=현재 문자의 다음 문자
-
-
-
반환 문자열
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def get_smallest_string(A): n = len(A) character = 'a' string = "" if (n < 1 or A[0] != 1): return -1 string += str(character) character = chr(ord(character) + 1) for i in range(1, n): difference = A[i] - A[i - 1] if (difference > 1 or difference < 0 or A[i] > 26): return -1 elif (difference == 0): string += 'a' else: string += character character = chr(ord(character) + 1) return string A = [1, 1, 2, 3, 4] print(get_smallest_string(A))
입력
[1, 1, 2, 3, 4]
출력
aabcd