Überprüfen Sie, ob die Zeichenfolge der durch ein Muster definierten Reihenfolge der Zeichen entspricht oder nicht | Satz 3
Anhand einer Eingabezeichenfolge und eines Musters wird überprüft, ob die Zeichen in der Eingabezeichenfolge derselben Reihenfolge folgen, die durch die im Muster vorhandenen Zeichen bestimmt wird. Gehen Sie davon aus, dass das Muster keine doppelten Zeichen enthält.
Beispiele:
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.
Wir haben zwei Ansätze zur Lösung dieses Problems diskutiert.
Überprüfen Sie, ob die Zeichenfolge der durch ein Muster definierten Reihenfolge der Zeichen entspricht oder nicht | Satz 1
Überprüfen Sie, ob die Zeichenfolge der durch ein Muster definierten Reihenfolge der Zeichen entspricht oder nicht | Satz 2
Bei diesem Ansatz weisen wir den Musterzeichen zunächst eine Bezeichnung (oder Reihenfolge) zu. Die Beschriftungen werden in aufsteigender Reihenfolge vergeben.
Beispielsweise wird das Muster „gsr“ wie folgt beschriftet
'g' => 1 's' => 2 'r' => 3
Das bedeutet, dass „g“ zuerst kommt, dann „s“ und dann „r“.
Nachdem wir Musterzeichen Beschriftungen zugewiesen haben, durchlaufen wir Zeichenfolgenzeichen. Beim Durchlaufen behalten wir die Bezeichnung (oder Reihenfolge) des zuletzt besuchten Zeichens im Auge. Wenn die Bezeichnung des aktuellen Zeichens kleiner als die des vorherigen Zeichens ist, geben wir „false“ zurück. Andernfalls aktualisieren wir das letzte Etikett. Wenn alle Zeichen der Reihenfolge entsprechen, geben wir true zurück.
Nachfolgend finden Sie die Implementierung
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>
Ausgabe
false
Zeitkomplexität dieses Programms ist An) mit konstantem zusätzlichem Speicherplatz (die Array-Beschriftung hat eine konstante Größe von 256).
Hilfsraum: O(256).
