简答题
偏难
#18053
字符排序 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有 n 个仅包含小写字母的字符串s 1 ,s 2 ,...,s n ,小杨想将这些字符…
字符排序
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有 n 个仅包含小写字母的字符串s1,s2,...,sn,小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串 t 。小杨希望最后构成的字符串 t 满足:
假设ti为字符串 t 的第 i 个字符,对于所有的j<i 均有tj≤ti。两个字符的大小关系与其在字母表中的顺序一致,例如e<g<p<s。
小杨想知道是否存在满足条件的字符串排列顺序。
输入格式
第一行包含一个正整数 T ,代表测试数据组数。
对于每组测试数据,第一行包含一个正整数 n ,含义如题面所示。
之后 n 行,每行包含一个字符串si。
输出格式
对于每组测试数据,如果存在满足条件的排列顺序,输出 1,否则输出 0。
输入样例
输出样例
样例解释
对于第一组测试数据,一种可行的排列顺序为 aa+ac+de,构成的字符串 t 为 aaacde,满足条件。
对于全部数据,保证有1≤t,n≤100,每个字符串的长度不超过 10。
答案与解析
正确答案:<pre class="brush:python;toolbar:false">def bubble_sort(a):
n, flag = len(a), True
while flag:
flag = False
for i in range(n - 1):
if a[i] > a[i + 1]:
flag = True
a[i], a[i + 1] = a[i + 1], a[i]
t = int(input())
for _ in range(t):
n = int(input())
s = []
for _ in range(n):
s.append(input())
bubble_sort(s)
t = ''.join(s)
fl = 1
for i in range(1, len(t)):
if t[i] < t[i - 1]:
fl = 0
break
print(fl)</pre>
这道题暂未补解析。