تحقق مما إذا كانت السلسلة تتبع ترتيب الأحرف المحددة بواسطة النمط أم لا | مجموعة 3
بالنظر إلى سلسلة إدخال ونمط، تحقق مما إذا كانت الأحرف في سلسلة الإدخال تتبع نفس الترتيب الذي تحدده الأحرف الموجودة في النمط. افترض أنه لن يكون هناك أي أحرف مكررة في النمط.
أمثلة:
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.
لقد ناقشنا طريقتين لحل هذه المشكلة.
تحقق مما إذا كانت السلسلة تتبع ترتيب الأحرف المحددة بواسطة النمط أم لا | مجموعة 1
تحقق مما إذا كانت السلسلة تتبع ترتيب الأحرف المحددة بواسطة النمط أم لا | مجموعة 2
في هذا الأسلوب، نقوم أولاً بتعيين تسمية (أو ترتيب) لأحرف النمط. يتم تعيين التسميات بترتيب متزايد.
على سبيل المثال، تم تسمية النمط "gsr" على النحو التالي
'g' => 1 's' => 2 'r' => 3
وهذا يعني أن "g" سيأتي أولاً ثم "s" ثم "r"
بعد تعيين تسميات لأحرف النمط، نقوم بالتكرار من خلال أحرف السلسلة. أثناء العبور، نقوم بتتبع التصنيف (أو الطلب) لآخر شخصية تمت زيارتها. إذا كانت تسمية الحرف الحالي أقل من الحرف السابق فإننا نعيد خطأ. وإلا فإننا نقوم بتحديث التسمية الأخيرة. إذا اتبعت جميع الشخصيات الترتيب نعود صحيحًا.
أدناه هو التنفيذ
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>
الإخراج
false
تعقيد الوقت من هذا البرنامج هو على) مع مساحة إضافية ثابتة (تسمية الصفيف ذات حجم ثابت 256).
المساحة المساعدة: O(256).
