给定一个字符串,问是否能通过添加一个字母将其变为回文串。 输入描述: 一行一个由小写字母构成的字符串,字符床长度小于等于10。 输出描述: 输出答案(YES\NO). 输入例子: coco 输出例子: YES
/**
*判断原字符串和翻转字符串的最长公共子序列长度是否比原字符串长度小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");
}
}
}
}