一个的只由小写英文字母组成的矩阵 ,牛牛想找到一个面积最小的正方形子矩阵满足该正方形子矩阵包含至少种不同的字母。
第一行输入三个正整数。
接下来 行每行输入一个长度为 的字符串,其中第 行第 个字母为 。
其中 为所有小写英文字母'a'-'z'的集合。
输出一个正整数表示包含至少 种不同字母的方形子矩阵的边长,如果不存在该子方阵,输出。
4 4 3 aabc aaaa axaz abcd
2
不存在边长为 的方形子矩阵包含至少 种不同的字母。
如图,存在边长为 的方形子矩阵包含至少 种不同的字母:
2 2 5 ab cd
-1
显然矩阵总共只有 种字符,因此答案为 。
class Solution: def check(self, n, m, s, k, pre): # s表示边长 # pre[i][j][t]表示以array[i][j]为右下角元素,array[0][0]为左上角元素正方形内 字母t出现的次数 for i in range(1, n+1): for j in range(1, m+1): if i + s -1 > n&nbs***bsp;j + s - 1 > m: continue count = 0 for t in range(26): if pre[i+s-1][j+s-1][t]-pre[i+s-1][j-1][t]-pre[i-1][j+s-1][t]+pre[i-1][j-1][t]>=1: count += 1 if count >= k: return True return False def minSideLength(self, array, n, m, k): import math pre = [[[0]*26 for _ in range(m+1)] for _ in range(n+1)] for i in range(1, n+1): for j in range(1, m+1): for t in range(26): pre[i][j][t] = pre[i-1][j][t] + pre[i][j-1][t] - pre[i-1][j-1][t] t = ord(array[i-1][j-1]) - ord("a") pre[i][j][t] += 1 minS, maxS = int(math.sqrt(k)), min(n, m) res = -1 while minS <= maxS: midS = (minS + maxS)>>1 if self.check(n, m, midS, k, pre): maxS = midS -1 res = midS else: minS = midS + 1 return res if __name__ == "__main__": [n, m, k] = list(map(int, input().strip().split())) array = [] for i in range(n): string = input() array.append(string) s = Solution() res = s.minSideLength(array, n, m, k) print(res)请问Python 3这样写有问题吗?老是显示超时 是语言的问题吗