数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 Python 中查找满足给定条件的字典序最小的字符串
假设我们有一个包含 n 个数字的数组 A，其中 A[i] 表示字符串 s 长度为 (i + 1) 的前缀中不同字符的数量，我们需要找到满足给定前缀数组的字典序最小的字符串。所有字符都将是小写英文字母 [a-z]。如果没有这样的字符串，则返回 -1。
因此，如果输入类似于 A = [1,1,2,3,4]，则输出将为 aabcd，因为 prefix[0] 有 1 个不同字符，prefix[1] 有 1 个不同字符，prefix[2] 有 2 个不同字符，prefix[3] 有 3 个不同字符，prefix[4] 有 4 个不同字符，并且字符串是最小的。
为了解决这个问题，我们将遵循以下步骤：
n := A 的大小
character := 'a'
string := 空字符串
如果 n < 1 或 A[0] 不为 1，则
返回 -1
string := string 拼接 character
character := 当前字符的下一个字符
对于 i 范围从 1 到 n，执行以下操作：
difference := A[i] - A[i - 1]
如果 difference > 1 或 difference < 0 或 A[i] > 26，则
返回 -1
否则，当 difference 等于 0 时，
string := string 拼接 'a'
否则，
string := string 拼接 character
character := 当前字符的下一个字符
返回 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
更新于：2020 年 8 月 20 日
373 次浏览
广告