Como posso calcular o número de caracteres necessários para transformar uma string em um palíndromo?
-
19-09-2019 - |
Pergunta
Eu encontrei recentemente um problema concurso que pede-lhe para calcular o número mínimo de caracteres que deve ser inserido (em qualquer lugar) em uma string para transformá-lo em um palíndromo.
Por exemplo, dada a string: "abcbd" podemos transformá-lo em um palíndromo, inserindo apenas dois personagens: um após "a" e outro depois de "d": "a d bcbd < b> a ".
Esta parece ser uma generalização de um problema semelhante que pede a mesma coisa, exceto caracteres só podem ser adicionados no final -. Isso tem uma solução bastante simples em O (N), utilizando tabelas de hash
Eu tenho tentado modificar a Levenshtein algoritmo distância para resolver este problema, mas haven' t sido bem sucedida. Qualquer ajuda sobre como resolver isso (não necessariamente tem que ser eficiente, só estou interessado em qualquer solução DP) seria apreciada.
Solução
Nota: Esta é apenas uma curiosidade. Dav proposto um algoritmo que pode ser modificado para algoritmo DP para ser executado em O (n ^ 2) tempo e O (n ^ 2) espaço facilmente (e talvez O (n) com uma melhor contabilidade).
É claro, esse algoritmo 'ingênuo' pode realmente vir a calhar se você decidir mudar as operações permitidas.
Aqui está um 'algoritmo naive'ish, que provavelmente pode ser feito mais rápido com a contabilidade inteligente.
Dado uma string, que acho meio do palíndromo resultante e, em seguida, tentar calcular o número de inserções necessário para fazer a seqüência de um palíndromo em torno desse meio.
Se a string é de comprimento n, existem 2n + 1 middles possíveis (cada personagem, entre dois personagens, um pouco antes e logo após a string).
Suponha que consideramos um meio que nos dá duas cadeias L e R (uma para a esquerda e um para a direita).
Se estamos usando inserções, eu acredito que o algoritmo Longest Subsequence Comum (que é um DP algoritmo) agora pode ser usado a criar uma seqüência de 'super' que contém ambos L e reverter de R, consulte comum Shortest Superseqüência .
Escolha o meio que lhe dá os menores inserções numéricas.
Este é O (n ^ 3) eu acredito. . (Nota: provar Eu não tentei que é verdade)
Outras dicas
Meu C aparência # solução para caracteres repetidos em uma string e usa-los para reduzir o número de inserções. Em uma palavra como programa , eu uso os personagens 'R' como um limite. Dentro do 'r do que faço que um palíndromo (de forma recursiva). Fora do 'r, I espelhar os caracteres à esquerda e à direita.
Algumas entradas têm mais de uma saída menor: saída pode ser toutptuot ou outuputuo . Minha solução seleciona apenas uma das possibilidades.
Alguns exemplos de corridas:
- radar -> radar , 0 inserções
- esystem -> metsystem , 2 inserções
- Mensagem -> megassagem , 3 inserções
- Stackexchange -> stegnahckexekchangets , 8 inserções
Primeiro eu preciso verificar se uma entrada já é um palíndromo:
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;
}
Então eu preciso encontrar quaisquer caracteres utilizadas na entrada. Pode haver mais de um. A palavra Mensagem tem dois personagens mais repetidas ( 'E' 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;
}
O meu algoritmo é aqui:
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;
}
}
Note que você precisa de uma função inversa:
public static string Reverse(string str)
{
string result = "";
for (int i = str.Length - 1; i >= 0; i--)
{
result += str[i];
}
return result;
}
C # solução recursiva adicionando ao final da string:
Existem 2 casos base. Quando o comprimento é 1 ou 2. caso recursiva: Se os extremos são iguais, então fazer palindrome a coluna interna sem os extremos e retorno que com os extremos. Se os extremos não são iguais, em seguida, adicione o primeiro caractere até o fim e fazer palindrome o coluna interna, incluindo o último caractere anterior. devolver isso.
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];
}
}