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'']