Me estoy preparando para una pregunta de entrevista. Una de las preguntas es revertir una oración. Por ejemplo, "es un día increíble" a "un día increíble". Después de esto, preguntaron si hay duplicación, ¿puedes eliminar la duplicación? .
para invertir la oración que he escrito siguiendo el método
public static string reversesentence(string one) { StringBuilder builder = new StringBuilder(); string[] split = one.Split(' '); for (int i = split.Length-1; i >= 0; i--) { builder.Append(split[i]); builder.Append(" "); } return builder.ToString(); }Pero no tengo ideas sobre cómo eliminar la duplicación. ¿Puedo obtener ayuda aquí?
Esto funciona:
public static string reversesentence(string one) { Regex reg = new Regex("\\w+"); bool isFirst = true; var usedWords = new HashSet<String>(StringComparer.InvariantCultureIgnoreCase); return String.Join("", one.Split(' ').Reverse().Select((w => { var trimmedWord = reg.Match(w).Value; if (trimmedWord != null) { var wasFirst = isFirst; isFirst = false; if (usedWords.Contains(trimmedWord)) //Is it duplicate? return w.Replace(trimmedWord, ""); //Remove the duplicate phrase but keep punctuation usedWords.Add(trimmedWord); if (!wasFirst) //If it's the first word, don't add a leading space return " " + w; return w; } return null; }))); }Básicamente, decidimos si es distinto en función de la palabra sin puntuación. Si ya existe, simplemente devuelva la puntuación. Si no existe, imprima la palabra completa, incluida la puntuación.
La puntuación también elimina el espacio en su ejemplo, por lo que no podemos simplemente hacer String.Join(" ", ...) (de lo contrario, el resultado sería good he Is , am I en lugar de good he Is, am I
Prueba:
reversesentence("I am good, Is he good").Dump();
Resultado:
good he Is, am I
Para inversión simple:
String.Join(" ", text.Split(' ').Reverse())Para reversión con eliminación duplicada:
String.Join(" ", text.Split(' ').Reverse().Distinct()) Ambos funcionan bien para cadenas que contienen solo espacios como separador. Cuando introduces el , el problema se vuelve más difícil. Tanto es así que es necesario especificar cómo se debe manejar. Por ejemplo, ¿debería "I am good, Is he good" convertirse en "good he Is am I" o "good he Is , am I" ? Su ejemplo en la pregunta cambia el caso de "Is" y agrupa el "," con él también. Eso me parece equivocado.
La otra respuesta apunta al uso de abstracciones, pero los entrevistadores generalmente quieren ver la implementación.
Para la inversión, el truco habitual es invertir primero la oración y luego invertir cada palabra a medida que avanza de izquierda a derecha. Un espacio te indicará que has llegado al final de una palabra. (Consulte Programación de entrevistas expuestas para obtener una solución a esto o simplemente búsquelo en Google. Esta solía ser una pregunta de entrevista MUY popular). Su enfoque funciona, pero está mal visto porque está utilizando espacio adicional (O (n)).
Para eliminar duplicados, si solo está trabajando con ASCII, puede hacer lo siguiente:
bool[] seenChars = new bool[128]; var sb = new StringBuilder(); foreach(char c in stringOne) { if(!seenChars[c]){ seenChars[c] = true; sb.Append(c); } } return sb.ToString();La idea es usar el valor del carácter como un índice en la matriz para decirle si ha visto este carácter antes o no. ¡Con este enfoque, usará el espacio O(1)!
Editar: si desea desduplicar palabras, probablemente desee usar un HashSet y omitir agregarlo si ya existe.