Compruebe si la cadena sigue el orden de los caracteres definidos por un patrón o no | Conjunto 3
Dada una cadena de entrada y un patrón, verifique si los caracteres en la cadena de entrada siguen el mismo orden determinado por los caracteres presentes en el patrón. Suponga que no habrá caracteres duplicados en el patrón.
Ejemplos:
Input: string = 'engineers rock' pattern = 'er'; Output: true All 'e' in the input string are before all 'r'. Input: string = 'engineers rock' pattern = 'egr'; Output: false There are two 'e' after 'g' in the input string. Input: string = 'engineers rock' pattern = 'gsr'; Output: false There are one 'r' before 's' in the input string.
Hemos discutido dos enfoques para resolver este problema.
Compruebe si la cadena sigue el orden de los caracteres definidos por un patrón o no | Conjunto 1
Compruebe si la cadena sigue el orden de los caracteres definidos por un patrón o no | Conjunto 2
En este enfoque, primero asignamos una etiqueta (u orden) a los caracteres del patrón. Las etiquetas se asignan en orden creciente.
Por ejemplo, el patrón 'gsr' está etiquetado de la siguiente manera
'g' => 1 's' => 2 'r' => 3
Significa que 'g' vendrá primero, luego 's' y luego 'r'.
Después de asignar etiquetas a los caracteres del patrón, repetimos los caracteres de cadena. Mientras atravesamos, realizamos un seguimiento de la etiqueta (u orden) del último carácter visitado. Si la etiqueta del carácter actual es menor que el carácter anterior, devolvemos falso. De lo contrario, actualizamos la última etiqueta. Si todos los caracteres siguen el orden, devolvemos verdadero.
A continuación se muestra la implementación.
C++ // C++ program to find if a string follows order // defined by a given pattern. #include using namespace std ; const int CHAR_SIZE = 256 ; // Returns true if characters of str follow // order defined by a given ptr. bool checkPattern ( string str string pat ) { // Initialize all orders as -1 vector < int > label ( CHAR_SIZE -1 ); // Assign an order to pattern characters // according to their appearance in pattern int order = 1 ; for ( int i = 0 ; i < pat . length () ; i ++ ) { // give the pattern characters order label [ pat [ i ]] = order ; // increment the order order ++ ; } // Now one by check if string characters // follow above order int last_order = -1 ; for ( int i = 0 ; i < str . length (); i ++ ) { if ( label [ str [ i ]] != -1 ) { // If order of this character is less // than order of previous return false. if ( label [ str [ i ]] < last_order ) return false ; // Update last_order for next iteration last_order = label [ str [ i ]]; } } // return that str followed pat return true ; } // Driver code int main () { string str = 'engineers rock' ; string pattern = 'gsr' ; cout < < boolalpha < < checkPattern ( str pattern ); return 0 ; }
Java // Java program to find if a string follows order // defined by a given pattern. class GFG { static int CHAR_SIZE = 256 ; // Returns true if characters of str follow // order defined by a given ptr. static boolean checkPattern ( String str String pat ) { int [] label = new int [ CHAR_SIZE ] ; // Initialize all orders as -1 for ( int i = 0 ; i < CHAR_SIZE ; i ++ ) label [ i ] = - 1 ; // Assign an order to pattern characters // according to their appearance in pattern int order = 1 ; for ( int i = 0 ; i < pat . length (); i ++ ) { // give the pattern characters order label [ pat . charAt ( i ) ] = order ; // increment the order order ++ ; } // Now one by check if string characters // follow above order int last_order = - 1 ; for ( int i = 0 ; i < str . length (); i ++ ) { if ( label [ str . charAt ( i ) ] != - 1 ) { // If order of this character is less // than order of previous return false. if ( label [ str . charAt ( i ) ] < last_order ) return false ; // Update last_order for next iteration last_order = label [ str . charAt ( i ) ] ; } } // return that str followed pat return true ; } // Driver code public static void main ( String [] args ) { String str = 'engineers rock' ; String pattern = 'gsr' ; System . out . println ( checkPattern ( str pattern )); } } // This code is contributed by // sanjeev2552
Python3 # Python3 program to find if a string follows # order defined by a given pattern CHAR_SIZE = 256 # Returns true if characters of str follow # order defined by a given ptr. def checkPattern ( Str pat ): # Initialize all orders as -1 label = [ - 1 ] * CHAR_SIZE # Assign an order to pattern characters # according to their appearance in pattern order = 1 for i in range ( len ( pat )): # Give the pattern characters order label [ ord ( pat [ i ])] = order # Increment the order order += 1 # Now one by one check if string # characters follow above order last_order = - 1 for i in range ( len ( Str )): if ( label [ ord ( Str [ i ])] != - 1 ): # If order of this character is less # than order of previous return false if ( label [ ord ( Str [ i ])] < last_order ): return False # Update last_order for next iteration last_order = label [ ord ( Str [ i ])] # return that str followed pat return True # Driver Code if __name__ == '__main__' : Str = 'engineers rock' pattern = 'gsr' print ( checkPattern ( Str pattern )) # This code is contributed by himanshu77
C# // C# program to find if a string follows order // defined by a given pattern. using System ; class GFG { static int CHAR_SIZE = 256 ; // Returns true if characters of str follow // order defined by a given ptr. static bool checkPattern ( String str String pat ) { int [] label = new int [ CHAR_SIZE ]; // Initialize all orders as -1 for ( int i = 0 ; i < CHAR_SIZE ; i ++ ) label [ i ] = - 1 ; // Assign an order to pattern characters // according to their appearance in pattern int order = 1 ; for ( int i = 0 ; i < pat . Length ; i ++ ) { // give the pattern characters order label [ pat [ i ]] = order ; // increment the order order ++ ; } // Now one by check if string characters // follow above order int last_order = - 1 ; for ( int i = 0 ; i < str . Length ; i ++ ) { if ( label [ str [ i ]] != - 1 ) { // If order of this character is less // than order of previous return false. if ( label [ str [ i ]] < last_order ) return false ; // Update last_order for next iteration last_order = label [ str [ i ]]; } } // return that str followed pat return true ; } // Driver code public static void Main ( String [] args ) { String str = 'engineers rock' ; String pattern = 'gsr' ; Console . WriteLine ( checkPattern ( str pattern )); } } // This code is contributed by 29AjayKumar
JavaScript < script > // Javascript program to find if a string follows order // defined by a given pattern. let CHAR_SIZE = 256 ; // Returns true if characters of str follow // order defined by a given ptr. function checkPattern ( str pat ) { let label = new Array ( CHAR_SIZE ); // Initialize all orders as -1 for ( let i = 0 ; i < CHAR_SIZE ; i ++ ) label [ i ] = - 1 ; // Assign an order to pattern characters // according to their appearance in pattern let order = 1 ; for ( let i = 0 ; i < pat . length ; i ++ ) { // give the pattern characters order label [ pat [ i ]. charCodeAt ( 0 )] = order ; // increment the order order ++ ; } // Now one by check if string characters // follow above order let last_order = - 1 ; for ( let i = 0 ; i < str . length ; i ++ ) { if ( label [ str [ i ]. charCodeAt ( 0 )] != - 1 ) { // If order of this character is less // than order of previous return false. if ( label [ str [ i ]. charCodeAt ( 0 )] < last_order ) return false ; // Update last_order for next iteration last_order = label [ str [ i ]. charCodeAt ( 0 )]; } } // return that str followed pat return true ; } // Driver code let str = 'engineers rock' ; let pattern = 'gsr' ; document . write ( checkPattern ( str pattern )); // This code is contributed by rag2127 < /script>
Producción
false
Complejidad del tiempo de este programa es En) con espacio adicional constante (la etiqueta de la matriz tiene un tamaño constante 256).
Espacio Auxiliar: O(256).
