Preverite, ali niz sledi vrstnemu redu znakov, določenem z vzorcem ali ne | Komplet 3
Glede na vhodni niz in vzorec preverite, ali znaki v vhodnem nizu sledijo istemu vrstnemu redu, kot ga določajo znaki v vzorcu. Predpostavimo, da v vzorcu ne bo nobenih podvojenih znakov.
Primeri:
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.
Razpravljali smo o dveh pristopih za rešitev tega problema.
Preverite, ali niz sledi vrstnemu redu znakov, določenem z vzorcem ali ne | Komplet 1
Preverite, ali niz sledi vrstnemu redu znakov, določenem z vzorcem ali ne | Komplet 2
Pri tem pristopu najprej dodelimo oznako (ali vrstni red) znakom vzorca. Oznake so dodeljene v naraščajočem vrstnem redu.
Na primer vzorec 'gsr' je označen kot sledi
'g' => 1 's' => 2 'r' => 3
To pomeni, da bo najprej "g", nato "s" in nato "r"
Po dodelitvi oznak vzorčnim znakom ponavljamo znake nizov. Med prečkanjem spremljamo oznako (ali vrstni red) nazadnje obiskanega znaka. Če je oznaka trenutnega znaka manjša od prejšnjega znaka, vrnemo false. V nasprotnem primeru posodobimo zadnjo oznako. Če vsi znaki sledijo vrstnemu redu, vrnemo true.
Spodaj je izvedba
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>
Izhod
false
Časovna zapletenost tega programa je O(n) s konstantnim dodatnim prostorom (oznaka polja je konstantne velikosti 256).
Pomožni prostor: O(256).
