문자열이 패턴으로 정의된 문자 순서를 따르는지 확인 | 세트 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'이 옴을 의미합니다.
패턴 문자에 레이블을 할당한 후 문자열 문자를 반복합니다. 탐색하는 동안 마지막으로 방문한 캐릭터의 레이블(또는 순서)을 추적합니다. 현재 문자의 레이블이 이전 문자보다 작으면 false를 반환합니다. 그렇지 않으면 마지막 라벨을 업데이트합니다. 모든 문자가 순서를 따르면 true를 반환합니다.
아래는 구현입니다
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).
