经典指数          
原因
1434
浏览数
0
收藏数
 

给定一个字符串,问是否能通过添加一个字母将其变为回文串。 输入描述: 一行一个由小写字母构成的字符串,字符床长度小于等于10。 输出描述: 输出答案(YES\NO). 输入例子: coco 输出例子: YES

     举报   纠错  
该题目由题来君提供于 2015-10-08 16:59
 
切换
1 个答案

/**

*判断原字符串和翻转字符串的最长公共子序列长度是否比原字符串长度小1或相等

*/

importjava.util.*;

publicclassMain

{

    publicstaticintlcs(String s, String s1)

    {

        if(s == null|| s1 == null) {

            return0;

        }

        intm = s.length();

        intn = s1.length();

        int[][] dp = newint[m + 1][n + 1];

        dp[0][0] = 0;

        for(inti = 1; i < m; i++) {

            dp[0][i] = 0;

        }

        for(inti = 1; i < m; i++) {

            dp[i][0] = 0;

        }

        for(inti = 1;i < m + 1; i++) {

            for(intj = 1; j < n + 1; j++) {

                if(s.charAt(i - 1) == s1.charAt(j - 1)) {

                    dp[i][j] = dp[i - 1][j - 1] + 1;

                } else{

                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

                }

            }

        }

        returndp[m][n];

    }

     

    publicstaticvoidmain(String[] args) {

        Scanner scanner = newScanner(System.in);

        while(scanner.hasNext()) {

            String s= scanner.nextLine();

            String s1 = newStringBuilder(s).reverse().toString();

            intlen = lcs(s, s1);

            if(s.length() - len <= 1) {

                System.out.println("YES");

            } else{

                System.out.println("NO");

            }

        }

    }

}

举报   题来君 · 2015-12-29 23:29
 
切换
撰写答案