1360f.md

题目地址(F. Spy-string)

https://codeforces.com/problemset/problem/1360/f

题目描述

You are given 𝑛 strings 𝑎1,𝑎2,…,𝑎𝑛: all of them have the same length 𝑚. The strings consist of lowercase English letters.

Find any string 𝑠 of length 𝑚 such that each of the given 𝑛 strings differs from 𝑠 in at most one position. Formally, for each given string 𝑎𝑖, there is no more than one position 𝑗 such that 𝑎𝑖[𝑗]≠𝑠[𝑗].

Note that the desired string 𝑠 may be equal to one of the given strings 𝑎𝑖, or it may differ from all the given strings.

For example, if you have the strings abac and zbab, then the answer to the problem might be the string abab, which differs from the first only by the last character, and from the second only by the first.

Input
The first line contains an integer 𝑡 (1≤𝑡≤100) — the number of test cases. Then 𝑡 test cases follow.

Each test case starts with a line containing two positive integers 𝑛 (1≤𝑛≤10) and 𝑚 (1≤𝑚≤10) — the number of strings and their length.

Then follow 𝑛 strings 𝑎𝑖, one per line. Each of them has length 𝑚 and consists of lowercase English letters.

Output
Print 𝑡 answers to the test cases. Each answer (if it exists) is a string of length 𝑚 consisting of lowercase English letters. If there are several answers, print any of them. If the answer does not exist, print "-1" ("minus one", without quotes).

Example
inputCopy
5
2 4
abac
zbab
2 4
aaaa
bbbb
3 3
baa
aaa
aab
2 2
ab
bb
3 1
a
b
c
outputCopy
abab
-1
aaa
ab
z
Note
The first test case was explained in the statement.

In the second test case, the answer does not exist.

前置知识

• 枚举

公司

• 暂无

思路

由于我们和每一个单词最多只能和差一个字符。因此我们可以枚举差的那个字符的位置以及那个位置上的字符是什么。

一共有 m 个位置，每个位置有 26 个取值（26 个小写英文字母），因为枚举一个单词需要最多 26 * m 次比较，每次我们需要遍历单词进行比较是否和其最多差一个字符，这又需要 m 的时间，另外一个有 n 个单词。于是 总共就需要 26 * m ^ 2 * n 次比较。

算法：

• 枚举 (位置，修改后的字符)组合，如果某个组合能够满足题意，直接返回即可
• 在这里，我们先枚举 m 个位置 再枚举 26 个字符是 ok 的。先枚举 26 个字母，再枚举 m 个位置也是 ok 的。本质上都是枚举了 (位置，修改后的字符)组合。 位置不同也不会有剪枝的效果，这里不妨先枚举位置，再枚举修改后的字符。

为了逻辑清晰，我将判断是否合法的逻辑抽离为了 can 函数，具体见代码区。

关键点

• 枚举顺序

代码

• 语言支持：Python3

Python3 Code:

t = int(input())

# determin whether ans is at most one charactor diff from all elements of A
def can(m, n, ans, A):
    found = True
    for i in range(n):
        diff = 0
        # let's check
        for j in range(m):
            if ans[j] != A[i][j]:
                diff += 1
            if diff > 1:
                found = False
                break  # early return for a better performance
    return found


for _ in range(t):
    n, m = map(int, input().split(" "))
    A = [input() for _ in range(n)]
    found = False
    for i in range(m):
        # either be A[0] or one charactor differ from A[0]. Let's iterate
        for j in range(26):
            ans = list(A[0])
            ans[i] = chr(ord("a") + j)
            found = can(m, n, ans, A)
            if found:  # early return for a better performance
                break
        if found:  # early return for a better performance
            break
    if found:
        print("".join(ans))
    else:
        print(-1)

复杂度分析

• 时间复杂度：$O(m^2*n)$
• 空间复杂度：$O(1)$