문자열이 패턴으로 정의된 문자 순서를 따르는지 확인 | 세트 2
입력 문자열과 패턴이 주어지면 입력 문자열의 문자가 패턴에 있는 문자에 의해 결정된 것과 동일한 순서를 따르는지 확인합니다. 패턴에 중복된 문자가 없다고 가정합니다.
같은 문제에 대한 또 다른 해결책이 게시되었습니다. 여기 .
예:
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.
여기서의 아이디어는 주어진 문자열을 주어진 패턴으로 줄이는 것입니다. 패턴에 제공된 문자의 경우 문자열에 해당 문자만 유지합니다. 새 문자열에서 연속적으로 반복되는 문자를 삭제합니다. 수정된 문자열은 주어진 패턴과 같아야 합니다. 마지막으로 수정된 문자열을 주어진 패턴과 비교하고 그에 따라 true 또는 false를 반환합니다.
삽화:
str = 'bfbaeadeacc' pat[] = 'bac' 1) Remove extra characters from str (characters that are not present in pat[] str = 'bbaaacc' [f e and d are removed] 3) Removed consecutive repeating occurrences of characters str = 'bac' 4) Since str is same as pat[] we return true
다음은 위 단계의 구현입니다.
// C++ code for the above approach #include #include using namespace std ; bool followsPattern ( string str string pattern ) { // Insert all characters of pattern in a hash set unordered_set < char > patternSet ; for ( int i = 0 ; i < pattern . length (); i ++ ) { patternSet . insert ( pattern [ i ]); } // Build modified string (string with characters only from pattern are taken) string modifiedStr = str ; for ( int i = str . length () - 1 ; i >= 0 ; i -- ) { if ( patternSet . find ( str [ i ]) == patternSet . end ()) { modifiedStr . erase ( i 1 ); } } // Remove more than one consecutive occurrences of pattern characters from modified string for ( int i = modifiedStr . length () - 1 ; i > 0 ; i -- ) { if ( modifiedStr [ i ] == modifiedStr [ i - 1 ]) { modifiedStr . erase ( i 1 ); } } // After above modifications the length of modified string must be same as pattern length if ( pattern . length () != modifiedStr . length ()) { return false ; } // And pattern characters must also be same as modified string characters for ( int i = 0 ; i < pattern . length (); i ++ ) { if ( pattern [ i ] != modifiedStr [ i ]) { return false ; } } return true ; } int main () { string str = 'engineers rock' ; string pattern = 'er' ; cout < < 'Expected: true Actual: ' < < followsPattern ( str pattern ) < < endl ; str = 'engineers rock' ; pattern = 'egr' ; cout < < 'Expected: false Actual: ' < < followsPattern ( str pattern ) < < endl ; str = 'engineers rock' ; pattern = 'gsr' ; cout < < 'Expected: false Actual: ' < < followsPattern ( str pattern ) < < endl ; str = 'engineers rock' ; pattern = 'eger' ; cout < < 'Expected: true Actual: ' < < followsPattern ( str pattern ) < < endl ; return 0 ; } // This code is contributed by adityashatmfh
Java // Java program to check if characters of a string follow // pattern defined by given pattern. import java.util.* ; public class OrderOfCharactersForPattern { public static boolean followsPattern ( String str String pattern ) { // Insert all characters of pattern in a hash set Set < Character > patternSet = neHashSet <> (); for ( int i = 0 ; i < pattern . length (); i ++ ) patternSet . add ( pattern . charAt ( i )); // Build modified string (string with characters only from // pattern are taken) StringBuilder modifiedString = new StringBuilder ( str ); for ( int i = str . length () - 1 ; i >= 0 ; i -- ) if ( ! patternSet . contains ( modifiedString . charAt ( i ))) modifiedString . deleteCharAt ( i ); // Remove more than one consecutive occurrences of pattern // characters from modified string. for ( int i = modifiedString . length () - 1 ; i > 0 ; i -- ) if ( modifiedString . charAt ( i ) == modifiedString . charAt ( i - 1 )) modifiedString . deleteCharAt ( i ); // After above modifications the length of modified string // must be same as pattern length if ( pattern . length () != modifiedString . length ()) return false ; // And pattern characters must also be same as modified string // characters for ( int i = 0 ; i < pattern . length (); i ++ ) if ( pattern . charAt ( i ) != modifiedString . charAt ( i )) return false ; return true ; } // Driver program int main () { String str = 'engineers rock' ; String pattern = 'er' ; System . out . println ( 'Expected: true Actual: ' + followsPattern ( str pattern )); str = 'engineers rock' ; pattern = 'egr' ; System . out . println ( 'Expected: false Actual: ' + followsPattern ( str pattern )); str = 'engineers rock' ; pattern = 'gsr' ; System . out . println ( 'Expected: false Actual: ' + followsPattern ( str pattern )); str = 'engineers rock' ; pattern = 'eger' ; System . out . println ( 'Expected: true Actual: ' + followsPattern ( str pattern )); return 0 ; } }
Python3 # Python3 program to check if characters of # a string follow pattern defined by given pattern. def followsPattern ( string pattern ): # Insert all characters of pattern in a hash set patternSet = set () for i in range ( len ( pattern )): patternSet . add ( pattern [ i ]) # Build modified string (string with characters # only from pattern are taken) modifiedString = string for i in range ( len ( string ) - 1 - 1 - 1 ): if not modifiedString [ i ] in patternSet : modifiedString = modifiedString [: i ] + modifiedString [ i + 1 :] # Remove more than one consecutive occurrences # of pattern characters from modified string. for i in range ( len ( modifiedString ) - 1 0 - 1 ): if modifiedString [ i ] == modifiedString [ i - 1 ]: modifiedString = modifiedString [: i ] + modifiedString [ i + 1 :] # After above modifications the length of # modified string must be same as pattern length if len ( pattern ) != len ( modifiedString ): return False # And pattern characters must also be same # as modified string characters for i in range ( len ( pattern )): if pattern [ i ] != modifiedString [ i ]: return False return True # Driver Code if __name__ == '__main__' : string = 'engineers rock' pattern = 'er' print ( 'Expected: true Actual:' followsPattern ( string pattern )) string = 'engineers rock' pattern = 'egr' print ( 'Expected: false Actual:' followsPattern ( string pattern )) string = 'engineers rock' pattern = 'gsr' print ( 'Expected: false Actual:' followsPattern ( string pattern )) string = 'engineers rock' pattern = 'eger' print ( 'Expected: true Actual:' followsPattern ( string pattern )) # This code is contributed by # sanjeev2552
C# // C# program to check if characters of a string follow // pattern defined by given pattern. using System ; using System.Collections.Generic ; using System.Text ; class GFG { public static bool followsPattern ( String str String pattern ) { // Insert all characters of pattern in a hash set HashSet < char > patternSet = new HashSet < char > (); for ( int i = 0 ; i < pattern . Length ; i ++ ) patternSet . Add ( pattern [ i ]); // Build modified string (string with characters // only from pattern are taken) StringBuilder modifiedString = new StringBuilder ( str ); for ( int i = str . Length - 1 ; i >= 0 ; i -- ) if ( ! patternSet . Contains ( modifiedString [ i ])) modifiedString . Remove ( i 1 ); // Remove more than one consecutive occurrences of pattern // characters from modified string. for ( int i = modifiedString . Length - 1 ; i > 0 ; i -- ) if ( modifiedString [ i ] == modifiedString [ i - 1 ]) modifiedString . Remove ( i 1 ); // After above modifications the length of modified string // must be same as pattern length if ( pattern . Length != modifiedString . Length ) return false ; // And pattern characters must also be same // as modified string characters for ( int i = 0 ; i < pattern . Length ; i ++ ) if ( pattern [ i ] != modifiedString [ i ]) return false ; return true ; } // Driver program public static void Main ( String [] args ) { String str = 'engineers rock' ; String pattern = 'er' ; Console . WriteLine ( 'Expected: true Actual: ' + followsPattern ( str pattern )); str = 'engineers rock' ; pattern = 'egr' ; Console . WriteLine ( 'Expected: false Actual: ' + followsPattern ( str pattern )); str = 'engineers rock' ; pattern = 'gsr' ; Console . WriteLine ( 'Expected: false Actual: ' + followsPattern ( str pattern )); str = 'engineers rock' ; pattern = 'eger' ; Console . WriteLine ( 'Expected: true Actual: ' + followsPattern ( str pattern )); } } // This code is contributed by 29AjayKumar
JavaScript < script > // Javascript program to check if characters of a string follow // pattern defined by given pattern. function followsPattern ( str pattern ) { // Insert all characters of pattern in a hash set let patternSet = new Set (); for ( let i = 0 ; i < pattern . length ; i ++ ) patternSet . add ( pattern [ i ]); // Build modified string (string with characters only from // pattern are taken) let modifiedString = ( str ). split ( '' ); for ( let i = str . length - 1 ; i >= 0 ; i -- ) if ( ! patternSet . has ( modifiedString [ i ])) modifiedString . splice ( i 1 ); // Remove more than one consecutive occurrences of pattern // characters from modified string. for ( let i = modifiedString . length - 1 ; i > 0 ; i -- ) if ( modifiedString [ i ] == modifiedString [ i - 1 ]) modifiedString . splice ( i 1 ); // After above modifications the length of modified string // must be same as pattern length if ( pattern . length != modifiedString . length ) return false ; // And pattern characters must also be same as modified string // characters for ( let i = 0 ; i < pattern . length ; i ++ ) if ( pattern [ i ] != modifiedString [ i ]) return false ; return true ; } // Driver program let str = 'engineers rock' ; let pattern = 'er' ; document . write ( 'Expected: true Actual: ' + followsPattern ( str pattern ) + '
' ); str = 'engineers rock' ; pattern = 'egr' ; document . write ( 'Expected: false Actual: ' + followsPattern ( str pattern ) + '
' ); str = 'engineers rock' ; pattern = 'gsr' ; document . write ( 'Expected: false Actual: ' + followsPattern ( str pattern ) + '
' ); str = 'engineers rock' ; pattern = 'eger' ; document . write ( 'Expected: true Actual: ' + followsPattern ( str pattern ) + '
' ); // This code is contributed by rag2127 < /script>
산출:
Expected: true Actual: true Expected: false Actual: false Expected: false Actual: false Expected: true Actual: true
시간 복잡도: 문자를 제거하기 위해 deleteCharAt()를 사용하므로 위 구현의 시간 복잡도는 실제로 O(mn + n^2)입니다. 선형 시간에 작동하도록 위의 솔루션을 최적화할 수 있습니다. deleteCharAr()을 사용하는 대신 빈 문자열을 만들고 여기에 필요한 문자만 추가할 수 있습니다.
StringBuilder는 입력 문자열에 대해 작업하는 데 사용됩니다. StringBuilder는 변경 가능하지만 String은 변경 불가능한 객체이기 때문입니다. 새 문자열을 생성하려면 O(n) 공간이 필요하므로 추가 공간은 O(n)입니다.
우리는 이 문제를 해결하기 위해 두 가지 접근 방식을 더 논의했습니다.
문자열이 패턴으로 정의된 문자 순서를 따르는지 확인 | 세트 1
문자열이 패턴으로 정의된 문자 순서를 따르는지 확인 | 세트 3
