如何计算将字符串转换为回文所需的字符数?
-
19-09-2019 - |
题
我最近发现一个竞赛问题,要求您计算必须在字符串中(任何位置)插入以将其转换为回文的最小字符数。
例如,给定字符串:“abcbd”我们可以通过插入两个字符将其变成回文:一个在“a”之后,另一个在“d”之后:“AdBCBA".
这似乎是一个类似问题的概括,它要求相同的事情,除了字符只能在末尾添加 - 这有一个使用哈希表的 O(N) 非常简单的解决方案。
我一直在尝试修改 编辑距离算法 来解决这个问题,但是还没有成功。任何有关如何解决此问题的帮助(不一定必须高效,我只是对任何 DP 解决方案感兴趣)将不胜感激。
解决方案
笔记:这只是一个好奇心。Dav 提出了一种可以修改为 DP 算法的算法,以便轻松地在 O(n^2) 时间和 O(n^2) 空间中运行(也许 O(n) 具有更好的簿记功能)。
当然,如果您决定更改允许的操作,这种“天真的”算法实际上可能会派上用场。
这是一个“天真的”算法,通过巧妙的簿记可能可以使其更快。
给定一个字符串,我们猜测生成的回文串的中间,然后尝试计算使该字符串成为围绕该中间的回文串所需的插入次数。
如果字符串的长度为 n,则有 2n+1 个可能的中间值(每个字符位于两个字符之间,位于字符串之前和之后)。
假设我们考虑一个中间,它给我们两个字符串 L 和 R(一个向左,一个向右)。
如果我们使用插入件,我相信 最长公共子序列 算法(DP 算法)现在可用于创建一个“超级”字符串,其中包含 L 和 R 的逆序,请参阅 最短公共超序列.
选择中间插入数量最少的。
我相信这是 O(n^3) 。(笔记:我没有尝试证明这是真的)。
其他提示
我的 C# 解决方案查找字符串中的重复字符并使用它们来减少插入次数。用一句话来说就是 程序, ,我使用“r”字符作为边界。在“r”内部,我将其设为回文(递归地)。在“r”之外,我镜像左侧和右侧的字符。
某些输入具有多个最短输出: 输出 可 兜售 或者 输出普陀. 。我的解决方案只选择其中一种可能性。
一些示例运行:
- 雷达 -> 雷达, 0 次插入
- 生态系统 -> 元系统, 2 个插入
- 信息 -> 梅加萨海姆, 3 个插入
- 堆栈交换 -> 斯坦格纳克克切克变更, 8 个插入
首先,我需要检查输入是否已经是回文:
public static bool IsPalindrome(string str)
{
for (int left = 0, right = str.Length - 1; left < right; left++, right--)
{
if (str[left] != str[right])
return false;
}
return true;
}
然后我需要找到输入中任何重复的字符。可能有不止一个。这个单词 信息 有两个最常重复的字符(“e”和“s”):
private static bool TryFindMostRepeatedChar(string str, out List<char> chs)
{
chs = new List<char>();
int maxCount = 1;
var dict = new Dictionary<char, int>();
foreach (var item in str)
{
int temp;
if (dict.TryGetValue(item, out temp))
{
dict[item] = temp + 1;
maxCount = temp + 1;
}
else
dict.Add(item, 1);
}
foreach (var item in dict)
{
if (item.Value == maxCount)
chs.Add(item.Key);
}
return maxCount > 1;
}
我的算法在这里:
public static string MakePalindrome(string str)
{
List<char> repeatedList;
if (string.IsNullOrWhiteSpace(str) || IsPalindrome(str))
{
return str;
}
//If an input has repeated characters,
// use them to reduce the number of insertions
else if (TryFindMostRepeatedChar(str, out repeatedList))
{
string shortestResult = null;
foreach (var ch in repeatedList) //"program" -> { 'r' }
{
//find boundaries
int iLeft = str.IndexOf(ch); // "program" -> 1
int iRight = str.LastIndexOf(ch); // "program" -> 4
//make a palindrome of the inside chars
string inside = str.Substring(iLeft + 1, iRight - iLeft - 1); // "program" -> "og"
string insidePal = MakePalindrome(inside); // "og" -> "ogo"
string right = str.Substring(iRight + 1); // "program" -> "am"
string rightRev = Reverse(right); // "program" -> "ma"
string left = str.Substring(0, iLeft); // "program" -> "p"
string leftRev = Reverse(left); // "p" -> "p"
//Shave off extra chars in rightRev and leftRev
// When input = "message", this loop converts "meegassageem" to "megassagem",
// ("ee" to "e"), as long as the extra 'e' is an inserted char
while (left.Length > 0 && rightRev.Length > 0 &&
left[left.Length - 1] == rightRev[0])
{
rightRev = rightRev.Substring(1);
leftRev = leftRev.Substring(1);
}
//piece together the result
string result = left + rightRev + ch + insidePal + ch + right + leftRev;
//find the shortest result for inputs that have multiple repeated characters
if (shortestResult == null || result.Length < shortestResult.Length)
shortestResult = result;
}
return shortestResult;
}
else
{
//For inputs that have no repeated characters,
// just mirror the characters using the last character as the pivot.
for (int i = str.Length - 2; i >= 0; i--)
{
str += str[i];
}
return str;
}
}
请注意,您需要一个 Reverse 函数:
public static string Reverse(string str)
{
string result = "";
for (int i = str.Length - 1; i >= 0; i--)
{
result += str[i];
}
return result;
}
C# 添加到字符串末尾的递归解决方案:
有 2 个基本情况。当长度为1或2时。递归情况:如果极端是相等的,则将palindrome在没有极端的情况下使内部字符串返回。如果极端不相等,则将第一个字符添加到末端,并使Palindrome成为内部字符串,包括上一个字符。返回那个。
public static string ConvertToPalindrome(string str) // By only adding characters at the end
{
if (str.Length == 1) return str; // base case 1
if (str.Length == 2 && str[0] == str[1]) return str; // base case 2
else
{
if (str[0] == str[str.Length - 1]) // keep the extremes and call
return str[0] + ConvertToPalindrome(str.Substring(1, str.Length - 2)) + str[str.Length - 1];
else //Add the first character at the end and call
return str[0] + ConvertToPalindrome(str.Substring(1, str.Length - 1)) + str[0];
}
}