最长回文子串计算（fail）

题意：

给定一个字符串s，在s中找到最长的回文子字符串。您可以假设s的最大长度为1000。

例子：

　　输入： “babad” 输出： “bab” 注： “aba”也是一个有效的答案。

我的答案：

想法：既然是回文字符串，就表示字符串正序倒序是一样的，先假设有一个turnString，把字符串翻转；整体思想是：从第0个元素开始遍历字符串，当比较到第i个字符时，从0开始到(i-1)为起始，(i-1)为终止的所有子串都比较一遍，找出最长回文子串，然后i++，直到比较完为止：

public static String longestPalindrome(String s) {

        String str = String.valueOf(s.charAt(0));

        for(int i=0; i<s.length(); i++){

            for(int j=0; j<i; j++){

                String sp = turnString(s.substring(j, i+1));

                if((sp.equals(s.substring(j, i+1))) && sp.length()>str.length()){

                    str = s.substring(j, i+1);

                }

            }

        }

        return str;

    }

    public static String turnString(String str) {

        String s = "";

        for (int i = str.length() - 1; i >= 0; i--) {

            char c = str.charAt(i);

            s = s + c;

        }

        return s;

    }

问题：

时间复杂度过大。

基于每次都要比较这个问题，增大了时间复杂度，抓住回文字符串的一个特点：起始和结尾的字符是相同的，那么假设比较到了字符'a'，那么就可以当且仅当前边子串中有相同字符时才翻转比较，并且只比较以a开头的，这样就降低了很大的时间复杂度。

下面是优化过的方法，其中优化了turnString方法为isTurn方法，用来直接判断某字符串是否为回文字符串，除此之外还做了其他优化：

public static String longestPalindrome(String s) {

        String str = String.valueOf(s.charAt(0));

        for(int i=0; i<s.length(); i++){

            if(s.contains(String.valueOf(s.charAt(i)))){

                for(int j=0; j<i; j++){

                    if((s.charAt(i)==s.charAt(j)) && isTurn(s.substring(j, i+1)) && (i+1-j)>str.length()){

                        str = s.substring(j, i+1);

                        break;

                    }

                }

            }

        }

        return str;

    }

    public static boolean isTurn(String str) {

        boolean bool = false;

        String s = "";

        for (int i = str.length() - 1; i >= 0; i--) {

            char c = str.charAt(i);

            s = s + c;

        }

        if(s.equals(str))

            bool = true;

        return bool;

    }

问题：由于isTurn函数的原理是将字符串完全颠倒后比较，浪费时间，为了提高效率，改为字符级别的比较，还优化了加入了start和end两个整形变量，减少了没必要的字符串切割，修改后如下：

public static String longestPalindrome(String s) {

        int start=0,end=1;

        for(int i=0; i<s.length(); i++){

            if(s.contains(String.valueOf(s.charAt(i)))){

                for(int j=0; j<i; j++){

                    if((s.charAt(i)==s.charAt(j)) && isTurn(s.substring(j, i+1)) && (i+1-j)>(end-start)){

                        start = j;

                        end = i+1;

                        break;

                    }

                }

            }

        }

        return s.substring(start,end);

    }

    public static boolean isTurn(String str) {

        boolean bool = true;

        for(int i=0,j=str.length()-1; i<j; i++,j--){

            if(str.charAt(i) != str.charAt(j)){//若不相同，退出

                bool = false;

                break;

            }

        }

        return bool;

    }

但是效率上还是有问题，超过了leetcode规定的时间复杂度。

下面是LeetCode给的解决方案：

class Solution {

    public String longestPalindrome(String s) {

    int start = 0, end = 0;

    for (int i = 0; i < s.length(); i++) {

        int len1 = expandAroundCenter(s, i, i);

        int len2 = expandAroundCenter(s, i, i + 1);

        int len = Math.max(len1, len2);

        if (len > end - start) {

            start = i - (len - 1) / 2;

            end = i + len / 2;

        }

    }

    return s.substring(start, end + 1);

}

private int expandAroundCenter(String s, int left, int right) {

    int L = left, R = right;

    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {

        L--;

        R++;

    }

    return R - L - 1;

  }

}

这个方法很有意思，很好的利用了回文子串对称的特点。举个例子，字符串aba和字符串abba都是回文字符串，特点就是对称，只不过aba的对称中心是一个字母b，而abba的对称中心是bb两个字母。而且只需要考虑这两种状况即可，那么，我们就可以写一个函数，从第i个字符向周边幅散型比较，此时只有两种情况：

1 以第i个字符为中心幅散

2 以第i个和第i+1个两个字符为中心幅散。

这样比较起来就比我自己写的降低了更多的复杂度。也是利用会文字符串本身特点想出来的优质方法。

巴特西

最长回文子串计算（fail）

题意：

例子：

我的答案：

下面是LeetCode给的解决方案：

最新文章

热门文章