Sjekk om streng følger rekkefølgen av tegn definert av et mønster eller ikke | Sett 2
Gitt en inndatastreng og et mønster, sjekk om tegnene i inndatastrengen følger samme rekkefølge som bestemt av tegnene i mønsteret. Anta at det ikke vil være noen dupliserte tegn i mønsteret.
En annen løsning på samme problem er lagt ut her .
Eksempler:
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.
Ideen her er å redusere den gitte strengen til det gitte mønsteret. For tegn gitt i mønsteret beholder vi bare de tilsvarende tegnene i strengen. I den nye strengen sletter vi kontinuerlige gjentatte tegn. Den modifiserte strengen skal da være lik mønsteret som er gitt. Til slutt sammenligner vi modifisert streng med mønsteret som er gitt og returnerer true of false tilsvarende.
Illustrasjon:
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
Nedenfor er implementeringen av trinnene ovenfor.
// 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>
Produksjon:
Expected: true Actual: true Expected: false Actual: false Expected: false Actual: false Expected: true Actual: true
Tidskompleksitet: Tidskompleksiteten til implementeringene ovenfor er faktisk O(mn + n^2) da vi bruker deleteCharAt() for å fjerne tegn. Vi kan optimere løsningen ovenfor for å fungere i lineær tid. I stedet for å bruke deleteCharAr() kan vi lage en tom streng og bare legge til nødvendige tegn til den.
StringBuilder brukes til å operere på inndatastreng. Dette er fordi StringBuilder er mutbar mens String er uforanderlig objekt. Å lage en ny streng tar O(n) mellomrom, så ekstra plass er O(n).
Vi har diskutert ytterligere to tilnærminger for å løse dette problemet.
Sjekk om streng følger rekkefølgen av tegn definert av et mønster eller ikke | Sett 1
Sjekk om streng følger rekkefølgen av tegn definert av et mønster eller ikke | Sett 3
