讨论/题目交流/可有大佬帮忙看个题/
可有大佬帮忙看个题

不知道下面那个题有没有低时间复杂度的解法或者好的解法,正在学习中,希望大佬们不吝赐教。

题目描述
有一天wcc在学习回文串的时候开始了他的胡思乱想,他觉得光从字符串里面找出一个回文串不够炫酷,所以他打算在字符矩阵里面找出一个回文矩阵。
定义字符矩阵里的字符Mx, y,代表第x行,第y列的字符,回文矩阵怎么定义呢?
wcc想了个很简单的定义,那就是只要在矩阵里面找出一个长宽都至少为2的长方形,上下两条边都由相同的回文串组成就好了。再详细说一说就是,假设矩形的左上角为(x1, y1),右下角为(x2, y2),满足:
· y2 - y1 ≥ 1
· x2 - x1 ≥ 1
· Mx1,y1 Mx1,y1 + 1...Mx1, y2为回文串
· Mx2,y1 Mx2,y1 + 1...Mx2, y2为回文串
两个回文串完全一致
现在有一个N行M列的字符矩阵,wcc想知道是否存在一个回文矩阵。

输入
第一行两个空格分隔的整数N, M(1 ≤ N, M ≤ 3000)
接下来N行,每行M个小写字母

输出
输出仅包含一行,如果存在输出YES,不存在输出NO

样例输入
3 3
aba
abc
aba

样例输出
YES

展开讨论
Lueeo发起于 2020-02-23

排序,从上往下,查找每行的回文串,记录始末索引,比较其他行的该始末位置 是否与找到的一样。一旦不一样就break(后面行肯定也不一样了,一样的因为排序会聚在一起),重新找下一行的回文。找到一个就YES。最后都没有,No。

1