Mi solución de C# busca caracteres repetidos en una cadena y los utiliza para reducir el número de inserciones. En una palabra como programa, utilizo los caracteres 'r' como un límite. Dentro de las 'r's, hago de eso un palíndromo (recursivamente). Fuera de las 'r's, hago un espejo de los personajes de la izquierda y la derecha.
Algunas entradas tienen más de una salida más corta: de salida puede ser toutptuot o outuputuo. Mi solución solo selecciona una de las posibilidades.
Algunos ejemplo ejecuta:
- radar ->radar, 0 inserciones
- esystem ->metsystem, 2 inserciones
- mensaje ->megassagem , 3 inserciones
- StackExchange ->stegnahckexekchangets, 8 inserciones
En primer lugar tengo que comprobar si hay una entrada que ya es un 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;
}
entonces necesito encontrar caracteres repetidos en la entrada . Puede haber más de uno. La palabra mensaje tiene dos personajes más repetidos ('e' y '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;
}
Mi algoritmo es aquí:
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;
}
}
Tenga en cuenta que se necesita una función inversa:
public static string Reverse(string str)
{
string result = "";
for (int i = str.Length - 1; i >= 0; i--)
{
result += str[i];
}
return result;
}
@IVlad - excelente pregunta. He eliminado el bit de introducción y he añadido un enlace al artículo de Wikipedia sobre Levenshtein. Espero que esté bien. Bienvenido a Stack Overflow! –
Me olvidé de preguntar, ¿es esta tarea? –
No es tarea. Fue un problema dado en una olimpíada de ciencias de la computación en mi país hace unos años, solo me interesaba la solución ya que no podía encontrar una oficial ni encontrar un DP por mi cuenta. – IVlad