Quiero saber cómo generar una expresión regular que detecte todas las combinaciones de una expresión regular dentro de una palabra. Por ejemplo:

Las coincidencias para "MAKE" deberían devolver "M", "MA", "MAK", "MAKE", "AKE", "AK", "A", "KE, "K", "E"

Entonces, la expresión regular para todos estos valores posibles es [A-Za-z]+

El problema es cómo recupero todos los valores posibles de una sola palabra:

Regex regex = new Regex( "[A-Za-z]+" );
foreach( Match m in regex.Matches( word ) )
{
    for( int i = 0; i < m.Groups.Count; i++ )
        Console.WriteLine( m.Groups[i].Value );
}

Solo me recupera "HACER" pero quiero agrupar todas las coincidencias dentro de esta palabra.

2
Fuczi Fuczi 20 oct. 2017 a las 00:39

3 respuestas

La mejor respuesta

Así que estaba tratando de acercarme a un generador de subcadenas de cadena con Regex. Tuve la idea, pero no estaba tan claro para mí, pero finalmente tuve un enfoque. No lo he probado tanto, pero ahora funciona y crea todas las subcadenas posibles (de izquierda a derecha) para una palabra desconocida de tamaño variable.

Funciona para C # Regex Engine. ¿No ha realizado una evaluación comparativa ni una complejidad calculada (Parece O (N ^ 2)?).

Quería tener un enfoque diferente para un problema que me dieron en una entrevista de Microsoft hace un par de horas. El punto era encontrar todas las palabras posibles dentro de una matriz de N palabras de tamaño N (en el ejemplo a continuación, 4 palabras de tamaño 4) en diagonal, horizontal y vertical (de izquierda a derecha y de arriba a abajo).

    static void CheckWords( String[] words, HashSet<String> valid )
    {
        //Horizontal
        foreach( var w in words )
            FindWords( w, valid );

        //Vertical
        String word = "";
        for( int i = 0; i < words.Length; i++ )
        {
            for( int j = 0; j < words[i].Length; j++ )
                word += words[j][i];

            FindWords( word, valid );
            word = "";
        }

        //Diagonal
        String word2 = "";
        for( int i = 0, j = 0; i < words.Length; i++, j++ )
        {
            word += words[i][j];
            word2 += words[i][words[i].Length - i - 1];
        }

        FindWords( word, valid );
        FindWords( word2, valid );

    }

    static void FindWords( String word, HashSet<string> valid )
    {
        int len = word.Length;
        //Generate all possible (left to right) substring for String with Length - a [ FOr example, for "MAKE" we can have possible values for "MAKE", "MAK", "MA", "M", "AKE", "KE", "K, "E", "A
        for( int a = 0; a < len; a++ )
        {
            //Find all possible substring with this length { k = 1, k = 2, k = 3, ..., k = word.Length }
            for( int k = 1; k <= word.Length; k++ )
            {
                Match match = new Regex(@"([A-Za-z]{" + k + "}){1}").Match(word);
                //For all found groups, we just care for the first group wich contains the main unrepeated substrings
                for( int i = 0; i < match.Groups.Count - 1; i++ )
                    for( int j = 0; j < match.Groups[i].Captures.Count; j++ ) //Check each permutation for each word with K length. You can Console.Write each value to check it's generated string
                        if( valid.Contains( match.Groups[i].Captures[j].Value ) )
                            Console.WriteLine( match.Groups[i].Captures[j].Value );
            }
            word = word.Substring( 1, word.Length - 1 );
        }
    }

Entonces, dada esta entrada:

    HashSet<String> words = new HashSet<string>();
    words.Add( "MAKE" );
    words.Add( "MAD" );         
    words.Add( "END" ); 
    words.Add( "MINE" );                

    String[] array = { "MAKE", "IEMY", "NIAH", "ENDN" };

    CheckWords( array, words );

Debería encontrar las cuatro palabras dentro de la matriz en el diccionario.

1
Fuczi Fuczi 20 oct. 2017 a las 02:48

Puedes hacerlo así

((((M)(?=(((A)K)E))A)(?=((K)E))K)(?=(E))E)

Hay una forma programática de construir una expresión regular usando una palabra dada.
Así es como hice esta expresión regular a mano. Lo dejaré como un ejercicio para que lo despliegue.

 **  Grp 0 -  ( pos 0 : len 4 ) 
MAKE  
 **  Grp 1 -  ( pos 0 : len 4 ) 
MAKE  
 **  Grp 2 -  ( pos 0 : len 3 ) 
MAK  
 **  Grp 3 -  ( pos 0 : len 2 ) 
MA  
 **  Grp 4 -  ( pos 0 : len 1 ) 
M  
 **  Grp 5 -  ( pos 1 : len 3 ) 
AKE  
 **  Grp 6 -  ( pos 1 : len 2 ) 
AK  
 **  Grp 7 -  ( pos 1 : len 1 ) 
A  
 **  Grp 8 -  ( pos 2 : len 2 ) 
KE  
 **  Grp 9 -  ( pos 2 : len 1 ) 
K  
 **  Grp 10 -  ( pos 3 : len 1 ) 
E  

Formateada y los detalles sangrientos:

 (                             # (1 start)
      (                             # (2 start)
           (                             # (3 start)
                ( M )                         # (4)
                (?=
                     (                             # (5 start)
                          (                             # (6 start)
                               ( A )                         # (7)
                               K
                          )                             # (6 end)
                          E
                     )                             # (5 end)
                )
                A
           )                             # (3 end)
           (?=
                (                             # (8 start)
                     ( K )                         # (9)
                     E
                )                             # (8 end)
           )
           K
      )                             # (2 end)
      (?=
           ( E )                         # (10)
      )
      E
 )                             # (1 end)
0
user557597user557597 19 oct. 2017 a las 22:40

Si solo necesita una expresión regular para que coincida con todas las subcadenas contiguas de "MAKE", puede usar lo siguiente:

^(M(|A(|K(|E)))|A(|K(|E))|K(|E)|E)$

Alternativamente, si no le importa el inicio y el final de la coincidencia de cadenas, puede acortarlo a:

M(|A(|K(|E)))|A(|K(|E)|K(|E)|E
0
Oliver Too Eh 19 oct. 2017 a las 22:46