Longest Palindrome Substring
利用子结构, 构造新的回文字符串.
init: dp[i][i] = true; dp[i][i+1]=true if s(i)==s(i+1)
iterate: dp[i][i+len] = dp[i+1][i+len-2]&&s.charAt(i)==s.charAt(i+len-1)
超时了 87/94 pass. 超时的case是"ddd...dd", 达到了n^2的复杂度.
public class Solution {
public String longestPalindrome(String s) {
if(s==null || s.length()==0) return s;
boolean[][] dp = new boolean[s.length()][s.length()];
String result = s.charAt(0)+"";
for(int i=0;i<s.length();i++){
dp[i][i]=true;
if(i<s.length()-1 && s.charAt(i)==s.charAt(i+1)){
dp[i][i+1] = true;
result = s.substring(i,i+2);
}
}
// System.out.println(dp[1][1]);
for(int l=3;l<=s.length();l++){
for(int i=0;i+l<=s.length();i++){
// System.out.println(i+ " " + (i+l-2) + " " + dp[i][i+l-2]);
// System.out.println("" + (s.charAt(i)==s.charAt(i+l-1)));
if(dp[i+1][i+l-2] && s.charAt(i)==s.charAt(i+l-1)){
result = s.substring(i, i+l);
dp[i][i+l-1] = true;
}
}
}
// System.out.println(dp[0][2]);
return result;
}
}
更好的方式是从一个字符串开始,向两边扩展, 直到不能再扩张为止.
public class Solution {
public String longestPalindrome(String s) {
if(s==null || s.length()==0) return "";
String longest = "";
for(int i=0;i<s.length();i++){
String tmp = helper(s, i, i);
if(tmp.length()> longest.length()){
longest = tmp;
}
tmp = helper(s, i, i+1);
if(tmp.length()> longest.length()){
longest = tmp;
}
}
return longest;
}
public String helper(String s, int begin, int end){
while(begin>=0 && end <s.length() && s.charAt(begin)==s.charAt(end)){
begin--;end++;
}
return s.substring(begin+1, end);
}
}
这道题用后缀树有O(n) time的解法, O(n) space. http://blog.csdn.net/v_july_v/article/details/6897097
对单词XMADAMYX而言，回文中心为D，那么D向右的后缀DAMYX假设是S(i)（当N=8，i从1开始计数，i=4时，便是S(4..8)）;而对于翻转后的单词XYMADAMX而言，回文中心D向右对应的后缀为DAMX，也就是S'(N-i+1)(（N=8，i=4，便是S‘（5..8））。此刻已经可以得出，它们共享最长前缀，即LCA（DAMYX，DAMX）=DAM。有了这套直观解释，算法自然呼之欲出：
- 预处理后缀树，使得查询LCA的复杂度为O(1)。这步的开销是O(N)，N是单词S的长度 ；
- 对单词的每一位置i(也就是从0到N-1)，获取LCA(S(i), S‘(N-i+1)) 以及LCA(S(i+1), S’(n-i+1))。查找两次的原因是我们需要考虑奇数回文和偶数回文的情况。这步要考察每坨i，所以复杂度是O(N) ；
- 找到最大的LCA，我们也就得到了回文的中心i以及回文的半径长度，自然也就得到了最长回文。总的复杂度O(n)。
Manacher's Algorithm https://discuss.leetcode.com/topic/12944/22-line-c-manacher-s-algorithm-o-n-solution
O(n)
Valid Palindrome
空字符串定义为true
ASC II 表里，一个字母的小写值与大写值的差正好是32 （小写字母值更大）
Character.isLetterOrDigit(char chr)
str.toLowerCase();
public class Solution {
public boolean isPalindrome(String s) {
// keypoint
//Character.isDigit Character.isLetter Character.toLower
if(s==null || s.length()==0) return true;
int start = 0; int end = s.length()-1;
while(start<end){
while(start<end &&(!Character.isDigit(s.charAt(start)) && !Character.isLetter(s.charAt(start)))) start++;
while(start<end && (!Character.isDigit(s.charAt(end)) && !Character.isLetter(s.charAt(end)))) end--;
if(start>=end) break;
if(Character.toLowerCase(s.charAt(start))!=Character.toLowerCase(s.charAt(end))) return false;
start++; end--;
}
return true;
}
}
Palindrome Permutation II
简答的DFS+backtracking, 开始出错的一个地方是忘记判断map里的<key,value> value只有大于0的时候才能使用. 否则"aabb" 会产生"aaaa" "bbbb" 这样的错误解
public class Solution {
public List<String> generatePalindromes(String s) {
List<String> result = new ArrayList<String>();
String start = "";
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
map.put(c, map.getOrDefault(c, 0)+1);
}
for(Character key : map.keySet()){
if(map.get(key)%2==1){
if(start.length()>0) return result;
start = key+"";
map.put(key, map.get(key)-1);
}
}
helper(map, new StringBuilder(start), s, result);
return result;
}
public void helper(HashMap<Character, Integer> map, StringBuilder sb, String s, List<String> list){
if(sb.length()==s.length()){
list.add(sb.toString());
return;
}
for(Character key : map.keySet()){
if(map.get(key)>0){
sb.append(key);
sb.insert(0, key);
map.put(key, map.get(key)-2);
helper(map, sb, s, list);
sb.deleteCharAt(0);
sb.deleteCharAt(sb.length()-1);
map.put(key, map.get(key)+2);
}
}
}
}
Shortest Palindrome
边看NBA边写代码, 用暴力思路,选定字符后朝两边扫描, 右边余下子串翻转后补齐, 注意初始化时, ans=substring(1), 注意边界条件, 判断left==-1&&right-1>=0; 超时 119/120 cases
public class Solution {
public String shortestPalindrome(String s) {
if(s==null || s.length()==0) return s;
String ans = s.substring(1);
for(int i=0;i<s.length();i++){
int left = i-1; int right =i+1;
while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
left--;right++;
}
if(left==-1 && right-1>=0 && s.substring(right).length()<ans.length()){
ans = s.substring(right);
System.out.println(i + " " + left + " " + ans);
}
left = i-1; right =i;
while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
left--;right++;
}
if(left==-1 && right-1>=0 && s.substring(right).length()<ans.length())
ans = s.substring(right);
}
return new StringBuilder(ans).reverse().toString()+s;
}
}
暴力解法
String reverse，"aacecaaa" ==> "aaacecaa"
找反转后的string和原string公共部分
a(aacecaa)
(aacecaa)a
从i==0到n-1开始枚举，如果str.substring(0,n-i)==reverse.substring(i)
return reverse.substring(0,i)+str
string shortestPalindrome(string s)
{
int n = s.size();
string rev(s);
reverse(rev.begin(), rev.end());
int j = 0;
for (int i = 0; i < n; i++) {
if (s.substr(0, n - i) == rev.substr(i))
return rev.substr(0, i) + s;
}
return "";
}
需要用KMP算法, 跳转KMP
public class Solution {
public String shortestPalindrome(String s) {
StringBuilder sb = new StringBuilder(s);
sb = new StringBuilder(s+"#"+sb.reverse().toString());
System.out.println(sb.toString());
int[] table = new int[sb.length()];
int j=0; int i=1;
for(;i<table.length;i++){
if(sb.charAt(i)==sb.charAt(j)){
table[i] = table[i-1]+1;
j++;
}
else{
j = table[i-1];
while(j>0&&sb.charAt(i)!=sb.charAt(j)){
j=table[j-1];
}
if(sb.charAt(i)==sb.charAt(j)){
j++;
}
table[i] = j;
}
}
int val = table[table.length-1];
System.out.println(Arrays.toString(table));
StringBuilder ans = new StringBuilder(s.substring(val)).reverse();
return ans.toString()+s;
}
}
Largest Palindrome Product
这道题起初以为有什么数学推导，后来发现没有。先按照n生成upper bound和lower bound，在[lower, upper] 中枚举half palindrome，看能不能被成功分解。
注意判断curp%j<=upper
createP只能创建length为偶数的Palindrome。n==1时，return 9
public class Solution {
public int largestPalindrome(int n) {
if(n==1) return 9;
int upper = (int)Math.pow(10,n)-1; int lower = (int)Math.pow(10,n-1)+1;
for(int i=upper;i>=lower;i--){
long curp = createP(i);
for(int j=upper;j>=lower;j--){
if(curp/j>upper) break;
else if(curp%j==0){
return (int)(curp%1337);
}
}
}
return -1;
}
public long createP(int i){
StringBuilder sb = new StringBuilder(i+"");
String ans = sb.toString()+sb.reverse().toString();
return Long.parseLong(ans);
}
}