今天某面试题,要在任意给定的字符串中,寻找最长回文串的长度。
注:回文串是指abc、abbc、aaabccc、aaaccc这种左右对称的字符串。
比如:abcaabbbaad字符串中,最长回文串的长度是7。
/**
* 思路:<br>
* 动态规划。一个指针从头往后遍历;一个指针从后往前遍历,把之前比较过的结果存到二维数组内,每个单元表示截止匹配到某一个字符串,所属的最长子串长度。<br>
* 因为从前往后和从后往前遍历是同一个串,所以这个二维数组是轴对称的。<br>
* 关键是这一步:当某时刻匹配上时,statArr[i][j] = statArr[j][i] = statArr[i - 1][j + 1] + 1,后一次的结果为前一次的结果加一。
*
* @author Ray Chase
*
*/
public final class SymmetricalSearch {
/**
* default constructor
*/
private SymmetricalSearch() {
}
/**
* 寻找最长的对称字符串长度
*
* @param word
* 被查字串
* @return 最长的字符串片段长度
*/
public static int getLongestSymmetricalSection(char[] word) {
// guard condition
if (null == word || 0 == word.length)
return 0;
// 存放状态的数组,取值表示最近一次匹配的字串长度
int[][] statArr = new int[word.length][word.length];
// 最长的字串的长度
int max = 0;
// 最近一行是否匹配上
boolean matched;
// i表示word自左向右方向遍历的指针,在动态规划的map中表示行号
for (int i = 0; i < word.length; i++) {
// 最近一行是否匹配上,每行开头预置位false
matched = false;
// j表示word自右向左方向遍历的指针,在动态规划的map中表示列号
for (int j = word.length - 1; j >= 0; j--) {
// 如果在边界,匹配上了
if (0 == i || word.length - 1 == j) {
if (word[i] == word[j]) {
matched = true;
statArr[i][j] = statArr[j][i] = 1;
}
}
// 不在边界且匹配上了,最近一次匹配的长度为上次匹配的长度+1
else if (word[i] == word[j]) {
matched = true;
statArr[i][j] = statArr[j][i] = statArr[i - 1][j + 1] + 1;
// 更新最长字串长度和字串起始位置
if (statArr[i][j] > max) {
max = statArr[i][j];
}
}
}
// 如果本行没有匹配上且当前发现的最大匹配长度已经大于等于剩下可能匹配的最大长度,没有必要继续了
if (!matched && max >= word.length - (i + 1)) {
break;
}
}
//不存在长度为1的对称字串
return 1 == max ? 0 : max;
}
}
这个算法其实还有改进的空间,譬如,动态规划不需要N平方的空间,因为每次使用这个statArr的时候,只用一行的数据,因此空间复杂度可以由n平方变为n。
具体的办法,还有其他改进的办法,欢迎大家讨论。:)
附,测试用例:
public class SynmetricalSearchTest extends TestCase {
public void testAbnormal() {
assertEquals(0, SymmetricalSearch.getLongestSymmetricalSection(null));
assertEquals(0, SymmetricalSearch.getLongestSymmetricalSection(""
.toCharArray()));
}
public void testOdd() {
assertEquals(5, SymmetricalSearch.getLongestSymmetricalSection("12321"
.toCharArray()));
assertEquals(3, SymmetricalSearch.getLongestSymmetricalSection("121"
.toCharArray()));
}
public void testEven() {
assertEquals(4, SymmetricalSearch.getLongestSymmetricalSection("1221"
.toCharArray()));
assertEquals(6, SymmetricalSearch.getLongestSymmetricalSection("123321"
.toCharArray()));
}
public void testMixOdd() {
assertEquals(5, SymmetricalSearch
.getLongestSymmetricalSection("asf12321drf".toCharArray()));
assertEquals(3, SymmetricalSearch.getLongestSymmetricalSection("121"
.toCharArray()));
}
public void testMixEven() {
assertEquals(4, SymmetricalSearch
.getLongestSymmetricalSection("6781221787".toCharArray()));
assertEquals(6, SymmetricalSearch
.getLongestSymmetricalSection("55512332144".toCharArray()));
}
public void testMixNone() {
assertEquals(0, SymmetricalSearch.getLongestSymmetricalSection("6784"
.toCharArray()));
}
public void testNesting() {
assertEquals(7, SymmetricalSearch
.getLongestSymmetricalSection("3332333".toCharArray()));
assertEquals(6, SymmetricalSearch
.getLongestSymmetricalSection("af323323ed".toCharArray()));
}
}
---------------------------------------------------------------------------------------------------------------------------------
2012-3-26 更新:
同事提点我,这个做法是有问题的,如果出现这样的字符串,比如:abcdba,这个做法会认为ab是最大子串,那就错了,因此,这个算法在每次发现疑似最大回文串时都要进行校验,当然,这样效率就低了不少。
网上比较多的相对比较简单的正确解法是后缀树解法,这里有一位高人的blog。
不过,小罗同学说,甚至可以把复杂度降到O(n)!太不可思议了是不是?据说这叫Manacher算法,看这里和这里。
文章系本人原创,转载请注明出处和作者
分享到:
相关推荐
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意: 假设字符串的长度不会超过 1010。 示例 1: 输入: ...
增强学习(三)MDP的动态规划解法增强学习(三)MDP的增强学习(三)MDP的动态规划解法动态规划解法
给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。 如果你可以用 s 中所有字符构造 k 个回文字符串,那么请你返回 True ,否则返回 False 。 示例 1: 输入:s = "annabelle", k...
旅行商问题-动态规划解法 旅行商问题-动态规划解法 旅行商问题-动态规划解法 旅行商问题-动态规划解法 旅行商问题-动态规划解法 旅行商问题-动态规划解法 旅行商问题-动态规划解法
计算机算法设计与分析题目解答,最长公共子序列的动态规划解法
125.验证回文串* [125] 验证回文串解法 1: 双指针。
双回文子串的后缀数组解法与应用,内含Bzoj例题与代码
Leetcode 1312. 让字符串成为回文串的最少插入次数问题描述1312. 让字符串成为回文串的最少插入次数 - 力扣(LeetCode)算法解法1: 递
输入一行字符串,找出其中出现的相同且长度最长的字符串,输入它及其首字符的位置。例如“yyabcdabjcabceg”,输出结果应该为abc和3.
解题思路:类似于矩阵连乘问题,可以用动态规划的方法来解决: (1)定义一个n*n的数组A来存储合并石子的最小合并方式,由一开始的只有两堆石子要合并慢慢向上递归得到n堆石子合并的最小得分。 (2)定义另一个...
多阶段决策过程( multistep decision process )是指这样一类特殊的活动过程,过程可以按时间顺序分解成若干个相互联系的阶段,在每一个阶段都需要做出决策,全部过程的决策是一个决策序列。在计算机算法设计方法中...
旅行商问题(Traveling Salesman Problem,TSP)是组合优化领域中著名的 NPhard问题, 具有较为广泛的工程应用和现实...本文先介绍一个简单的旅行商问题,并运用动态规划算法求解此问题。最后给出求解此问题所需要的代码。
一般数学模型的动态规划解法PPT学习教案.pptx
优化势在必行。 一些适用一类状态转移方程的优化:利用四边形不等式、函数的凸性等。 大多数状态转移方程的求解需要采用“个性化”的优化手段。
[6.4.1]--411找零兑换问题的动态规划解法.srt
[6.4.1]--411找零兑换问题的动态规划解法.mp4
某推销员要从城市v1 出发,访问其它城市v2,v3,…,v6 各一次且仅一次,最后返回v1。D 为各城市间的距离矩阵。 问:该推销员应如何选择路线,才能使总的行程最短?... 此代码是用动态规划方法,Linux下g++编译通过
回文数的五种解法一、题目描述二、题目解析1. 解题思路2. Python实现 一、题目描述 题目:9.回文数 难度:简单 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 示例 1:...
(2) 金罐游戏问题的动态规划解法。 算法设计与分析-4动态规划金罐游戏.pptx 蛮力法(简单重复递归)和动态规划解决金罐问题 状态数组 子问题 状态方程 蛮力法(时间复杂度O(2n))和动态规划(时间复杂度O(n2)) ...
算法实验中用动态规划法解0-1背包问题,这里提供了源代码,仅供参考