[译]最长回文字符串-阿里云开发者社区

开发者社区> 人工智能> 正文

[译]最长回文字符串

简介: 原文链接: Longest Palindromic Substring 找到最长回文字符串是一个经典的编码面试问题,本文总结了针对这个问题的3中不同的解决方案。

原文链接: Longest Palindromic Substring

找到最长回文字符串是一个经典的编码面试问题,本文总结了针对这个问题的3中不同的解决方案。

  1. 动态程序
    让s成为输入字符串,i和j是字符串的两个索引。定义一个二维数组“table”,让table[i][j]表示从i到j的子字符串是否为回文。

更改条件:

table[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j)
=>
table[i][j] == 1

时间 O(n^2) 空间 O(n^2)

public String longestPalindrome(String s) {
    if(s==null || s.length()<=1)
        return s;
 
    int len = s.length();
    int maxLen = 1;
    boolean [][] dp = new boolean[len][len];
 
    String longest = null;
    for(int l=0; l<s.length(); l++){
        for(int i=0; i<len-l; i++){
            int j = i+l;
            if(s.charAt(i)==s.charAt(j) && (j-i<=2||dp[i+1][j-1])){
                dp[i][j]=true;
 
                if(j-i+1>maxLen){
                   maxLen = j-i+1; 
                   longest = s.substring(i, j+1);
                }
            }
        }
    }
 
    return longest;
}

例如, 如果输入字符串是"dabcba", 最终的矩阵如下:

1 0 0 0 0 0 
0 1 0 0 0 1 
0 0 1 0 1 0 
0 0 0 1 0 0 
0 0 0 0 1 0 
0 0 0 0 0 1 

从表中,我们可以清楚地看到,最长的字符串是table[1][5]。

  1. 简单的算法
    时间 O(n^2), 空间 O(1)
public String longestPalindrome(String s) {
    if (s.isEmpty()) {
        return null;
    }
 
    if (s.length() == 1) {
        return s;
    }
 
    String longest = s.substring(0, 1);
    for (int i = 0; i < s.length(); i++) {
        // get longest palindrome with center of i
        String tmp = helper(s, i, i);
        if (tmp.length() > longest.length()) {
            longest = tmp;
        }
 
        // get longest palindrome with center of i, i+1
        tmp = helper(s, i, i + 1);
        if (tmp.length() > longest.length()) {
            longest = tmp;
        }
    }
 
    return longest;
}
 
// Given a center, either one letter or two letter, 
// Find longest palindrome
public String helper(String s, int begin, int end) {
    while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
        begin--;
        end++;
    }
    return s.substring(begin + 1, end);
}
  1. 曼切尔算法
    尽管它将带来O(n)时间复杂度的好处,但曼切尔算法的计算要复杂得多。因为它不是典型的,所以没有必要浪费时间。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章