本文出自 http://blog.csdn.net/shuangde800
题目大意
给一个字符串,输出它的最长回文串,如果有多个结果,输出字典序最小的。
思路
我们都知道把一个字符串逆序后和原字符串进最长公共子序列,可以计算出它的最长回文串长度。
但是这题不仅要输出回文串,而且还要求是字典序最小的,所以挺难搞的。
设str1是正序字符串,str2是逆序后的字符串
f[i][j].len 表示str1的前i位,str2的前j位,最长公共子串的长度
f[i][j].str 表示str1的前i位,str2的前j位,最长公共子串的最小字典序的字符串
状态转移和正常的LCS差不多,只不过增加了记录字典序最小的字符串
但是最终的f[i][j].str却并不一定是答案,因为计算出来的最长公共子序列不一定就是回文串
例如:
kfclbckibbibjccbej
jebccjbibbikcblcfk
bcibbibc是他们的LCS,但是却不是回文串
但是它的前len/2个一定是回文串的前半部分
知道了前len/2,就可以直接构造出回文串的后半部分了
要注意长度的奇偶性问题
代码
<script src="https://code.csdn.net/snippets/562.js" type="text/javascript"></script>
分享到:
相关推荐
USACO题目Palindromic Squares(回文平方数)及代码解析
回文串是指正反两个方向都一样的单词或短语,排列是指字母重新排列,回文串不一定是字典中的单词。 例如: 输入:“tactcoa” 输出:True(排列有“tacocat”、”atcocta”等等) 解答 思路: 所有字符中,统计每个...
Leetcode回文串拼接 leetcode_node 题解 该项目主要用于基于Leetcode的刷题记录,与日常学习,对Leetcode上的题目按照解题方法进行分明别类的整理。 题目列表 1.Two Sum 2.Add Two Numbers 3.Longest Substring ...
最长回文子序列 动态规划 | 第 12 组(最长回文子序列)( )
主要介绍了Python实现常见的回文字符串算法,本文通过实例代码给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
Palindromic Substring 中等 回文 ZigZag Conversion 中等 矩阵 重要 Reverse Integer 简单 字串 String to Integer (atoi) 中等 字串 麻烦 Palindrome Number 简单 字串 Container With Most Water 中等 动态规划 ...
Longest-Palindromic-Substring(最长回文子串) 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 Sample 1 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 Sample 2 输入...
Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container With Most Water 盛最多水的容器 13 Roman to Integer 罗马数字转整数 14 Longest Common Prefix 最长...
Palindromic Substring 最长回文子串 string,dp 8 String to Integer(atoi) 字符串转整数 string 13 Roman to Integer 罗马数字转整数 number,string 14 Longest Common Prefix 最长公共前缀 string 16 3Sum Closest...
Palindromic Substring 最长回文子串 6. ZigZag Conversion Z字型变换 7. Reverse Integer 整数反转 8. String to Integer (atoi) 字符串转换整数 (atoi) 9. Palindrome Number 回文数 10. Regular Expression ...
最长回文子串最长回文子串 | 设置 1 ( )
Palindromic Substring 最长回文子串,补符号,记忆 6. ZigZag Conversion 观察规律 7. Reverse Integer 翻转整数 8. String to Integer 解析字符串 9. Palindrome Number 回文数字 10. Regular Expression Matching...
zoj 3661 Palindromic Substring.md
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: ...
输入一个整数判断其是否是回文数……可以直接在vc6.0平台上 直接运行通过,例如输入 121 ,则输出,恭喜您,您输入的是回文数……呵呵,见笑了,学习学习……
回文数要确定是否需要取消费用,必须先确定是否需要取消费用。 Elnúmerodebe ser市长de 2dígitos。 Desarrollar unaaplicaciónque ingrese dosnúmerosy se cambien las posiciones pares del底漆númerocon el ...
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 示例 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. 示例 2: ...
leetcode 516 8/13 - 8/18 周:leetcode#: 409. longestPalindrome 125. Valid Palindrome 28. Implement strStr() ...Palindromic ...Palindromic Subsequence string replacement strStr II 链接:
400 题LeetCode solutions in Java 8 and Python3.NO.Title中文名...Palindromic Substring最长回文子串Java PythonNoteMediumtwo pointers dp backtracking5ZigZag ConversionZ字形变换Java PythonNoteMedium6...