Tjek, om strengen følger rækkefølgen af tegn defineret af et mønster eller ej | Sæt 2
Givet en inputstreng og et mønster, skal du kontrollere, om tegnene i inputstrengen følger samme rækkefølge som bestemt af tegn, der er til stede i mønsteret. Antag, at der ikke vil være nogen duplikerede tegn i mønsteret.
En anden løsning på samme problem er postet 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 at reducere den givne streng til det givne mønster. For tegn angivet i mønsteret beholder vi kun de tilsvarende tegn i strengen. I den nye streng sletter vi kontinuerlige gentagne tegn. Den modificerede streng skal så være lig med det givne mønster. Til sidst sammenligner vi modificeret streng med det givne mønster og returnerer true of false tilsvarende.
Illustration:
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 implementering af ovenstående trin.
// 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>
Produktion:
Expected: true Actual: true Expected: false Actual: false Expected: false Actual: false Expected: true Actual: true
Tidskompleksitet: Tidskompleksiteten af ovenstående implementeringer er faktisk O(mn + n^2), da vi bruger deleteCharAt() til at fjerne tegn. Vi kan optimere ovenstående løsning til at arbejde i lineær tid. I stedet for at bruge deleteCharAr() kan vi oprette en tom streng og kun tilføje nødvendige tegn til den.
StringBuilder bruges til at arbejde på inputstreng. Dette skyldes, at StringBuilder kan ændres, mens String er et uforanderligt objekt. For at oprette en ny streng tager O(n) mellemrum, så ekstra mellemrum er O(n).
Vi har diskuteret yderligere to tilgange til at løse dette problem.
Tjek, om strengen følger rækkefølgen af tegn defineret af et mønster eller ej | Sæt 1
Tjek, om strengen følger rækkefølgen af tegn defineret af et mønster eller ej | Sæt 3
