java - 如何将字符串转换为具有最少字符替换数的回文字符串，以便回文字符串包含给定的单词？

Question

我们有一个字符串 s，包含小写字母 (a-z)。我们可以用任何其他字符替换任何字符，我们可以这样做任意多次。

我们可以从s生成回文字符串p，这样p包含给定的特定单词(即让我们假设领英)。现在，我们需要找到将字符串 s 转换为 p 所需的最少插入次数。

ex - s = linkedinininin 那么回文字符串 p 将是 linkedinnideknil，结果将是 6。

第二个例子(让它更清楚)- s = linkaeiouideknil 然后 p = linkedinnideknil 并且结果将是 4，因为我们将用 e 替换 a，e 与 d、o 和 u 与 n。

我试图通过获取 s 和 p 的 LCS 并从 s 的长度中减去它来解决这个问题。但问题是我如何确保回文保证包含给定的单词(Linkedin)？

请提供您的方法。谢谢。

Answer 1

假设我正确理解了你的问题，

您可以创建回文，然后替换 s 中的错误字母:

String s="linkaeiouideknil";
String p="";
String word="linkedin";
char[] wordC = word.toCharArray();
StringBuilder sb = new StringBuilder();
sb.append(word);
String drow = sb.reverse().toString();
sb.reverse();
sb.append(drow);
String pali=sb.toString();
char[] sC = s.toCharArray();
sC=Arrays.copyOf(sC, pali.length());
sb.delete(0, sb.length());
int counter=0;
for (int i = 0; i < sC.length; i++) {
    if(sC[i]!=pali.charAt(i)){
        sC[i]=pali.charAt(i);
        counter++;
    }
    sb.append(sC[i]);
}
System.out.println(counter);    
p=sb.toString();
System.out.println(p);

运行时的输出为4。