Groep verschoven tekenreeks
Gegeven een array van strings (allemaal kleine letters) is het de taak om ze zo te groeperen dat alle strings in een groep verschoven versies van elkaar zijn.
Twee snaren s1 En s2 worden verschoven genoemd als aan de volgende voorwaarden is voldaan:
- s1.lengte is gelijk aan s2.lengte
- s1[ik] is gelijk aan s2[ik] + M voor alle 1 <= i <= s1.length for a constante geheel getal m. Beschouw de verschuiving als cyclisch, dat wil zeggen als s2[i] + m > 'z' en begin dan bij 'a' of als s2[i] + m < 'a' then start from 'z'.
Voorbeelden:
Invoer: arr[] = ['acd' 'dfg' 'wyz' 'yab' 'mop' 'bdfh' 'a' 'x' 'moqs']
Uitgang: [ ['acd' 'dfg' 'wyz' 'yab' 'mop'] ['bdfh' 'moqs'] ['a' 'x'] ]
Uitleg: Alle verschoven snaren zijn gegroepeerd.
Invoer: arr = ['nerd' 'voor' 'nerds']
Uitgang: [['voor'] ['nerd'] ['nerds']]
Aanpak: Hash Map gebruiken
C++Het idee is om een uniek exemplaar te genereren hasj voor elke groep door normaliseren de snaren. Hier normaliseren betekent dat het eerste teken van elke string gelijk wordt gemaakt aan 'a' door het vereiste te berekenen verschuivingen en het uniform toepassen op alle karakters in cyclische mode .
Voorbeeld: s = 'dca' verschuivingen = 'd' - 'a' = 3
genormaliseerde tekens: 'd' - 3 = 'a' 'c' - 3 = 'z' en 'a' - 3 = 'x'
genormaliseerde string = 'azx'De genormaliseerde reeks (hash) vertegenwoordigt de verschuivingspatroon zodat strings met hetzelfde patroon dezelfde hash hebben. We gebruiken een hashkaart om deze hashes bij te houden en ze in kaart te brengen in overeenkomstige groepen. Voor elke string berekenen we een hash en gebruiken deze om een nieuwe groep te creëren of om de string in één keer aan een bestaande groep toe te voegen.
// C++ program to print groups of shifted strings // together using Hash Map #include #include #include using namespace std ; // Function to generate hash by shifting and equating // the first character string getHash ( string s ) { // Calculate the shift needed to normalize the string int shifts = s [ 0 ] - 'a' ; for ( char & ch : s ) { // Adjust each character by the shift ch = ch - shifts ; // Wrap around if the character goes below 'a' if ( ch < 'a' ) ch += 26 ; } return s ; } // Function to group shifted string together vector < vector < string >> groupShiftedString ( vector < string > & arr ) { vector < vector < string >> res ; // Maps hash to index in result unordered_map < string int > mp ; for ( string s : arr ) { // Generate hash representing the shift pattern string hash = getHash ( s ); // If new hash create a new group if ( mp . find ( hash ) == mp . end ()) { mp [ hash ] = res . size (); res . push_back ({}); } // Add string to its group res [ mp [ hash ]]. push_back ( s ); } return res ; } int main () { vector < string > arr = { 'acd' 'dfg' 'wyz' 'yab' 'mop' 'bdfh' 'a' 'x' 'moqs' }; vector < vector < string >> groups = groupShiftedString ( arr ); for ( vector < string > & group : groups ) { for ( string & s : group ) { cout < < s < < ' ' ; } cout < < endl ; } return 0 ; }
Java // Java program to print groups of shifted strings // together using Hash Map import java.util.* ; class GfG { // Function to generate hash by shifting and equating the // first character static String getHash ( String s ) { // Calculate the shift needed to normalize the string int shifts = s . charAt ( 0 ) - 'a' ; char [] chars = s . toCharArray (); for ( int i = 0 ; i < chars . length ; i ++ ) { // Adjust each character by the shift chars [ i ] = ( char ) ( chars [ i ] - shifts ); // Wrap around if the character goes below 'a' if ( chars [ i ] < 'a' ) chars [ i ] += 26 ; } return new String ( chars ); } // Function to group shifted strings together static ArrayList < ArrayList < String >> groupShiftedString ( String [] arr ) { ArrayList < ArrayList < String >> res = new ArrayList <> (); // Maps hash to index in result HashMap < String Integer > mp = new HashMap <> (); for ( String s : arr ) { // Generate hash representing the shift pattern String hash = getHash ( s ); // If new hash create a new group if ( ! mp . containsKey ( hash )) { mp . put ( hash res . size ()); res . add ( new ArrayList <> ()); } // Add string to its group res . get ( mp . get ( hash )). add ( s ); } return res ; } public static void main ( String [] args ) { String [] arr = { 'acd' 'dfg' 'wyz' 'yab' 'mop' 'bdfh' 'a' 'x' 'moqs' }; ArrayList < ArrayList < String >> groups = groupShiftedString ( arr ); for ( ArrayList < String > group : groups ) { for ( String s : group ) { System . out . print ( s + ' ' ); } System . out . println (); } } }
Python # Python program to print groups of shifted strings # together using Hash Map # Function to generate hash by shifting and equating the first character def getHash ( s ): # Calculate the shift needed to normalize the string shifts = ord ( s [ 0 ]) - ord ( 'a' ) hashVal = [] for ch in s : # Adjust each character by the shift newCh = chr ( ord ( ch ) - shifts ) # Wrap around if the character goes below 'a' if newCh < 'a' : newCh = chr ( ord ( newCh ) + 26 ) hashVal . append ( newCh ) return '' . join ( hashVal ) # Function to group shifted strings together def groupShiftedString ( arr ): res = [] # Maps hash to index in result mp = {} for s in arr : # Generate hash representing the shift pattern hashVal = getHash ( s ) # If new hash create a new group if hashVal not in mp : mp [ hashVal ] = len ( res ) res . append ([]) # Add string to its group res [ mp [ hashVal ]] . append ( s ) return res if __name__ == '__main__' : arr = [ 'acd' 'dfg' 'wyz' 'yab' 'mop' 'bdfh' 'a' 'x' 'moqs' ] groups = groupShiftedString ( arr ) for group in groups : print ( ' ' . join ( group ))
C# // C# program to print groups of shifted strings // together using Hash Map using System ; using System.Collections.Generic ; class GfG { // Function to generate hash by shifting and equating the first character static string getHash ( string s ) { // Calculate the shift needed to normalize the string int shifts = s [ 0 ] - 'a' ; char [] chars = s . ToCharArray (); for ( int i = 0 ; i < chars . Length ; i ++ ) { // Adjust each character by the shift chars [ i ] = ( char )( chars [ i ] - shifts ); // Wrap around if the character goes below 'a' if ( chars [ i ] < 'a' ) chars [ i ] += ( char ) 26 ; } return new string ( chars ); } // Function to group shifted strings together static List < List < string >> groupShiftedString ( string [] arr ) { List < List < string >> res = new List < List < string >> (); // Maps hash to index in result Dictionary < string int > mp = new Dictionary < string int > (); foreach ( string s in arr ) { // Generate hash representing the shift pattern string hash = getHash ( s ); // If new hash create a new group if ( ! mp . ContainsKey ( hash )) { mp [ hash ] = res . Count ; res . Add ( new List < string > ()); } // Add string to its group res [ mp [ hash ]]. Add ( s ); } return res ; } static void Main ( string [] args ) { string [] arr = { 'acd' 'dfg' 'wyz' 'yab' 'mop' 'bdfh' 'a' 'x' 'moqs' }; var groups = groupShiftedString ( arr ); foreach ( var group in groups ) { Console . WriteLine ( string . Join ( ' ' group )); } } }
JavaScript // JavaScript program to print groups of shifted strings // together using Hash Map // Function to generate hash by shifting and equating the first character function getHash ( s ) { // Calculate the shift needed to normalize the string const shifts = s . charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 ); let chars = []; for ( let ch of s ) { // Adjust each character by the shift let newChar = String . fromCharCode ( ch . charCodeAt ( 0 ) - shifts ); // Wrap around if the character goes below 'a' if ( newChar < 'a' ) newChar = String . fromCharCode ( newChar . charCodeAt ( 0 ) + 26 ); chars . push ( newChar ); } return chars . join ( '' ); } // Function to group shifted strings together function groupShiftedString ( arr ) { const res = []; // Maps hash to index in result const mp = new Map (); for ( let s of arr ) { // Generate hash representing the shift pattern const hash = getHash ( s ); // If new hash create a new group if ( ! mp . has ( hash )) { mp . set ( hash res . length ); res . push ([]); } // Add string to its group res [ mp . get ( hash )]. push ( s ); } return res ; } // Driver Code const arr = [ 'acd' 'dfg' 'wyz' 'yab' 'mop' 'bdfh' 'a' 'x' 'moqs' ]; const groups = groupShiftedString ( arr ); groups . forEach ( group => console . log ( group . join ( ' ' )));
Uitvoer
acd dfg wyz yab mop bdfh moqs a x
Tijdcomplexiteit: O(n*k) waarbij n de lengte is van de stringarray en k de maximale lengte is van een string in de stringarray.
Hulpruimte: O(n*k) In het ergste geval kunnen we voor elke invoerreeks respectievelijk n verschillende hash-strings genereren. We hebben dus n verschillende vermeldingen in de hashkaart, elk met een lengte k of minder.
