我被分配了一个任务,要创建一个类,给定一个字符串,用最少的断言创建一个回文。
示例运行:
Input: 123333
Output: 12333321
Input: 789
Output: 78987
Input: 1221
Output: 1221221
注意回文不应该返回相同的回文。
我尝试使用修改过的KMP算法,如这里所述。
我将字符串反转并与反向+原始字符串进行比较,然后将不匹配项添加到原始字符串中。
然而,我的函数仅适用于具有尾随数字的输入(第一个示例输入),但类似于1234
的输入将返回1234123
,'92837465'将返回'928374659283746'
public static int[] computelps(String sample){
int[] lps = new int[sample.length()];
lps[0] = 0;
int i = 1;
int len = 0; // length of previous longest prefix suffix
while (i < sample.length()) {
if (sample.charAt(i) == sample.charAt(len)) {
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0) {
len = lps[len - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
public static void Solution(File samplefile) throws Exception {
BufferedReader br = new BufferedReader(new FileReader(samplefile));
String firstline = br.readLine();
String line;
while ((line = br.readLine()) != null) {
String reverse_str = "";
String newline = line.replace(".", "");
for (int i = newline.length() - 1; i >= 0; i--) {
reverse_str += newline.charAt(i);
}
int [] lps = computelps(reverse_str); // computes the lps of the pattern string
String tot = reverse_str + newline;
// KMP Algorithm modified.
int x = 0; // index for total_string(tot)
int y = 0; // index for pattern
String palindrome = newline;
while (x < tot.length()){
if(reverse_str.charAt(y) == tot.charAt(x)){
y++;
x++;
}
if(y == reverse_str.length()) {
y = lps[y - 1];
}
else if( x < tot.length() && (reverse_str.charAt(y) != tot.charAt(x))){
palindrome += tot.charAt(x);
if ( y!= 0){
y = lps[y-1];
}
else{
x += 1;
}
}
}
System.out.println(palindrome);
}
}
我很感激您的帮助。我认为算法非常具有挑战性,如果我的方法或代码不太好,请多多包容。
*我更正了样本输入和输出,并添加了我的结果。
1221
应该得到12211221
的输出?难道不应该是1221221
吗?因为这是创建回文所需的最少添加次数。 - Jordan