回文

[编程题]回文

热度指数：5013 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

京京和东东是好朋友。东东很喜欢回文。回文是指从前往后读和从后往前读是一样的词语。京京准备给东东一个惊喜,先取定一个字符串s,然后在后面附上 0 个或者更多个字母形成回文,京京希望这个回文越短越好。请帮助京京计算他能够得到的最短的回文长度。

数据范围：输入的字符串长度满足 $1\le n \le 100 \$ ，且保证只含有小写英文字母

输入描述:

输入包括一个字符串s,字符串s长度length

输出描述:

输出一个整数,表示牛牛能够得到的最短的回文长度。

示例1

输入

abab

输出

说明

在末尾添加一个 'a' 构成回文

示例2

输入

输出

说明

本身就是回文

算法知识视频讲解

Java

Mono_Chrome

找寻规律，从i=0开始判断这个改字符到最后一个字符是否是回文串，如果是，字符串长度加上i就是最终结果。

import java.util.Scanner;

public class Main {

    public static boolean isPalindrome(char[] ch, int i, int j) {
        while (i < j) {
            if (ch[i++] != ch[j--]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] ch = sc.next().toCharArray();
        for (int i = 0;  i < ch.length; i++) {
            if (isPalindrome(ch, i, ch.length - 1)) {
                System.out.println(ch.length  + i);
                break;
            }
        }
    }
}

发表于 2019-06-14 16:29:33 回复(0)