Ellenőrizze, hogy a karakterlánc követi-e a minta által meghatározott karakterek sorrendjét, vagy sem | 2. készlet
Adott egy bemeneti karakterlánc és egy minta ellenőrizze, hogy a bemeneti karakterlánc karakterei ugyanazt a sorrendet követik-e, mint amit a mintában jelen lévő karakterek határoznak meg. Tegyük fel, hogy nem lesznek ismétlődő karakterek a mintában.
Ugyanennek a problémának egy másik megoldása is megjelent itt .
Példák:
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.
Itt az az ötlet, hogy az adott karakterláncot a megadott mintára redukáljuk. A mintában megadott karaktereknél csak a megfelelő karaktereket tartjuk meg a karakterláncban. Az új karakterláncban töröljük a folyamatosan ismétlődő karaktereket. A módosított karakterláncnak ekkor egyenlőnek kell lennie a megadott mintával. Végül összehasonlítjuk a módosított karakterláncot a megadott mintával, és ennek megfelelően adjuk vissza a true értéket a false értékkel.
Ábra:
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
Az alábbiakban bemutatjuk a fenti lépések végrehajtását.
// 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>
Kimenet:
Expected: true Actual: true Expected: false Actual: false Expected: false Actual: false Expected: true Actual: true
Időbeli összetettség: A fenti megvalósítások időbeli összetettsége valójában O(mn + n^2), mivel a deleteCharAt()-t használjuk a karakterek eltávolítására. A fenti megoldást úgy tudjuk optimalizálni, hogy lineáris időben működjön. A deleteCharAr() használata helyett létrehozhatunk egy üres karakterláncot, és csak a szükséges karaktereket adhatjuk hozzá.
A StringBuilder a bemeneti karakterláncok kezelésére szolgál. Ennek az az oka, hogy a StringBuilder változtatható, míg a String megváltoztathatatlan objektum. Egy új karakterlánc létrehozása O(n) szóközt vesz igénybe, tehát az extra szóköz O(n).
A probléma megoldására további két megközelítést tárgyaltunk.
Ellenőrizze, hogy a karakterlánc követi-e a minta által meghatározott karakterek sorrendjét, vagy sem | 1. készlet
Ellenőrizze, hogy a karakterlánc követi-e a minta által meghatározott karakterek sorrendjét, vagy sem | 3. készlet
