【每日一练】中等难度

题目1、字符串全排列

限制：
时间限制：1000ms
内存限制：256M

题目描述：
对K个不同字符的全排列组成的数组, 面试官从中随机拿走了一个, 剩下的数组作为输入, 请帮忙找出这个被拿走的字符串? 比如[“ABC”, “ACB”, “BAC”, “CAB”, “CBA”] 返回 “BCA”

输入描述：
第一行输入整数n，表示给定n个字符串。(n == x!-1,2<=x<=10) 以下n行每行输入一个字符串。

输出描述：
输出全排列缺少的字符串。

示例

# 输入
5
ABC
ACB
BAC
CAB
CBA
# 输出
BCA
1
2
3
4
5
6
7
8
9

解题思路

计算n个字符串全排列，每个字符在各列出现的次数，出现次数最少的即为当前列缺少的元素。

代码

需要注意的是，当vector为空时，应当输出为空字符串，不然通过率无法达到100%。

def solution(n, vector):
    result = ""
    if len(vector) > 0:
        v_name = list(vector[0])
        len_v = len(v_name)
        for i in range(len_v):  
            counts = {key: 0 for key in v_name}  
            for str_v in vector:  
                if str_v[i] in counts:  
                    counts[str_v[i]] += 1  
            for key in counts:  
                if counts[key] < (n+1)//len_v :  
                    result += key  
    return result

if __name__ == "__main__":
    n = int(input().strip())
    vector = []
    for i in range(n):
        vector.append(input().strip())
    result = solution(n, vector)
    print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22