密码截取

密码截取

http://www.nowcoder.com/questionTerminal/3cd4621963e8454594f00199f4536bb1

和Leetcode 5 最长回文字是一个题,暴力解采用双指针从两侧向中心搜索,复杂度可达O(n^3)。这里我们采用中心扩散的做法,把复杂度降到O(n^2)。
所谓中心扩散,就是选定一个值,然后向左右扩散。我们可以发现,回文串有两种,一种是aabb,中心在ab之间;另一种是aacbb,中心为c。我们可以写一个方法,通过给left和right传入不同的初始index来实现这两种情况。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str = in.nextLine();
            int max = 0;
            for(int i = 0; i < str.length() - 1; i++){
                //aabaa的情况
                max = Math.max(max,longestPalindrome(str,i,i));
                //aabbaa的情况
                max = Math.max(max,longestPalindrome(str,i,i+1));
            }
            System.out.println(max);
        }
    }

    public static int longestPalindrome(String s, int left, int right){
        int len = 0;
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            len = right - left + 1;
            left--;
            right++;
        }
        return len;
    }
}
全部评论

相关推荐

07-02 13:52
门头沟学院 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 18:35
简历上把1个月实习写成了3个月,会进行背调吗?
码农索隆:一个月有一个月的实习经历,三个月有三个月的实习经历
点赞 评论 收藏
分享
重生我想学测开:嵌入式的问题,我准备入行京东外卖了
点赞 评论 收藏
分享
05-14 09:24
青岛工学院 C++
点赞 评论 收藏
分享
评论
29
5
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务