c# - variable - Escriba una función que compare dos cadenas y devuelva una tercera cadena que contenga solo las letras que aparecen en ambos

ejemplo de string

Question

Tengo esta tarea. Y lo he resuelto de la siguiente manera. Necesito sus comentarios si es un buen enfoque o si necesito usar cualquier otra estructura de datos para resolverlo de una mejor manera.

 public string ReturnCommon(string firstString, string scndString)
{
StringBuilder newStb = new StringBuilder();
if (firstString != null && scndString != null)
{
foreach (char ichar in firstString)
{
if (!newStb.ToString().Contains(ichar) && scndString.Contains(ichar))
newStb.Append(ichar);
}
}
return newStb.ToString();
}

Answer 1

Depende de cuánto tiempo son las cadenas de entrada, cuál es la letra y cómo debe verse el resultado (duplicados) hay algunos otros enfoques.

Por ejemplo:

Si las letras son solo caracteres [AZ] y cada letra debe aparecer solo una vez en la cadena de salida, puede construir cadenas separadas (o tablas de caracteres) ''ABC ... XZ'' (llamémosle letters ) y ejecutar for each ciclo sobre letters y compruebe ambas cadenas de entrada contra cada letra de las letters .

Esto proporciona 26 iteraciones de bucle y no más de 52 llamadas de método Contains() para cada cadena de entrada, sin importar cuánto tiempo sean las cadenas de entrada.

Answer 2

Eso está bien para un primer acercamiento, pero puedes hacer algunas mejoras, y hay un pequeño error.

• Si b contiene un carácter en a que ya está en c , lo repetirá.
• Para evitar repeticiones, puede considerar usar un Set para almacenar los caracteres, ya que un Set no tendrá repeticiones.
• Ensamblar cadenas con += concatenación suele ser ineficiente; Considere usar un StringBuilder o una clase análoga de ensamblaje de cadenas.
• Tus nombres de variables no son muy descriptivos.
• Si a o b están vacíos, ¡no tiene que hacer ningún trabajo en absoluto! Solo devuelve una cadena vacía.

También puede pensar en mejoras más sofisticadas, imaginando cómo se escalará su algoritmo si comenzó a utilizar cadenas de caracteres enormes. Por ejemplo, un enfoque podría ser que si una cadena es mucho más larga que la otra, puede ordenar la más larga y eliminar duplicados. Entonces puedes hacer una búsqueda binaria en los caracteres de la cadena más corta muy rápidamente.

Answer 3

Me parece bien, pero por Dios, ¡usa nombres de variables descriptivos!

Answer 4

Para mejorar la última sugerencia de John Feminella, más rápido que una búsqueda binaria (para una cadena suficientemente larga) sería una búsqueda en un hashset; o una búsqueda en una matriz de elementos de 256 elementos booleanos, si son caracteres ASCII o UTF8 en lugar de caracteres UTF16.

• Crea una instancia de hashset vacío o una matriz vacía de booleanos; nombrar esta variable found
• Para cada char en la primera cadena, agregue el carácter char al hashset (pero tenga cuidado con los caracteres duplicados en la primera cadena) o establezca el elemento correspondiente en la matriz found en verdadero; esto tomará tiempo O (n) lineal.
• Para cada char en la segunda cadena, compruebe si la char existe en el hashset o si el elemento correspondiente en la matriz ''found'' es verdadero: si se encuentra, entonces agregue el caracter a la cadena de retorno, y también elimine el caracter del hashset o borrar el elemento booleano en la matriz, para que no se vuelva a encontrar (tener cuidado con los caracteres duplicados en la segunda cadena); esto tomará tiempo O (n) lineal.

Answer 5

Se ve bien. Puede hacer un par de optimizaciones según el idioma que esté utilizando:

• puedes juntar las letras de b en una estructura ordenada (para hacer una búsqueda más rápida), y si no se repite ... mejor (un conjunto).
• puedes usar algún tipo de StrignBuilder (si es Java o .Net) para no recrear una cadena con cada concatenación dentro del ciclo

De todos modos, se trata de optimizaciones que son buenas para cadenas grandes y grandes ... por lo tanto, no sé si son adecuadas para su uso o para la tarea prevista.

Answer 6

Usando LINQ:

a.ToCharArray().Intersect<char>(b.ToCharArray())

Sin embargo, esto es sensible a mayúsculas.

Answer 7

Para una solución alternativa, puede ver las cadenas como enumerables y usar Intersect() esta manera:

 public static string Common(string first, string second)
{
return new string((first.Intersect(second)).ToArray());
}

Answer 8

FYI: Aquí está el código C / C ++:

/* Q: Write a function f(a, b) which takes two character string arguments
and returns a string containing only the characters found in both
strings in the order of a. */
#include <iostream>
#include <string>
#include <cstring>
#include <map>
using namespace std;
/* A: Unclear: repeated chars in string a? */
string CommonChars(const char* a, const char* b)
{
string result("");
if (!a || !b || !*a || !*b)
return result;
map<char, bool> hash;
int len1 = strlen(a), len2 = strlen(b);
for (int i = 0; i < len2; ++i)
hash[b[i]] = true;
for (int i = 0; i < len1; ++i)
{
map<char, bool>::iterator it = hash.find(a[i]);
if (it != hash.end() && it->second)
{
result += a[i];
hash[a[i]] = false; // OR: hash.erase(it);
}
}
return result;
}
int main()
{
cout << CommonChars("abcdefgbx", "gcfcba") << endl;
return 0;
}
/* Output:
abcfg
*/

Answer 9

Aquí mi solución en Python. Si no estoy equivocado, debería tomar el tiempo O (n) lineal.

# Write a function f(a, b) which takes two character string arguments
# and returns a string containing only the characters found in both
# strings in the order of a.
first_string = "attempt"
secong_string="tmay"
result = []
#it''s O(n) operation
for char in first_string:
if char in secong_string:
if char not in result:
result.append(char)
print result

los resultados se ven así:

[''a'', ''t'', ''m'']