关于算法：Java：如何通过插入最少字符数来创建字符串的最短回文？

Java: How to create the shortest palindrome of a string by inserting the minimum number of characters?

我目前有以下实现，它通过插入最少数量的字符来处理给定字符串的最短回文，但只处理前面的字符插入以创建最短回文。

但是通过以下实现，或者如果有更好的实现，我该如何在字符串中的任何点插入字符以使其成为回文？

将接受并投票赞成答案。谢谢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class Answer {
public String findShortestPalindrome(String s) {
int len = s.length();
if (len <= 1) {
return s;
}
int i = len – 1;
for (; i >= 0; —i) {
if (stringIsPalindrome(s, 0, i)) {
break;
}
}

StringBuilder sb = new StringBuilder(s.substring(i + 1));
sb.reverse().append(s);
return sb.toString();
}

public boolean stringIsPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end–;
}
return true;
}
}

差异
寻找处理插入字符串中任意点的最短回文。

相关讨论

我不认为这是乔所要求的。此外，您的 stringIsPalindrome 实际上比他的原始方法慢，因为它创建了一个额外的字符串，反转其中一个字符串，然后比较它们。
抱歉！我只是提出一个可能的解决方案

你可以实现以下蛮力算法：

如果输入字符串为空或由一个元素组成，则返回输入

如果字符串的第一个字符等于最后一个字符，则将该过程应用于输入字符串，没有第一个和最后一个项目

如果 first 和 last 不一样，那么你有两个选择：

1 2	left = last + palindromed(input without last) + last or right = first + palindromed(input without first) + first

所以在这一步你选择最短的解决方案

Java: How to create the shortest palindrome of a string by inserting the minimum number of characters?

猜你喜欢