Gruppenverschobene Zeichenfolge
Bei einem gegebenen Array von Zeichenfolgen (allesamt Kleinbuchstaben) besteht die Aufgabe darin, sie so zu gruppieren, dass alle Zeichenfolgen in einer Gruppe verschobene Versionen voneinander sind.
Zwei Saiten s1 Und s2 heißen verschoben, wenn folgende Bedingungen erfüllt sind:
- s1.Länge ist gleich s2.Länge
- s1[i] ist gleich s2[i] + M für alle 1 <= i <= s1.length for a Konstante Ganzzahl m. Betrachten Sie die Verschiebung als zyklisch, das heißt, wenn s2[i] + m > 'z', dann beginnen Sie bei 'a' oder wenn s2[i] + m < 'a' then start from 'z'.
Beispiele:
Eingang: arr[] = ['acd' 'dfg' 'wyz' 'yab' 'mop' 'bdfh' 'a' 'x' 'moqs']
Ausgabe: [ ['acd' 'dfg' 'wyz' 'yab' 'mop'] ['bdfh' 'moqs'] ['a' 'x'] ]
Erläuterung: Alle verschobenen Strings werden gruppiert.
Eingang: arr = ['geek' 'für' 'geeks']
Ausgabe: [['for'] ['geek'] ['geeks']]
Ansatz: Verwendung einer Hash-Map
C++Die Idee ist, ein Unikat zu generieren Hash für jede Gruppe von normalisierend die Saiten. Hier normalisierend bedeutet, das erste Zeichen jeder Zeichenfolge durch Berechnen des erforderlichen Werts gleich „a“ zu machen Verschiebungen und es einheitlich auf alle Zeichen in anwenden zyklische Mode .
Beispiel: s = 'dca' shifts = 'd' - 'a' = 3
normalisierte Zeichen: 'd' - 3 = 'a' 'c' - 3 = 'z' und 'a' - 3 = 'x'
normalisierte Zeichenfolge = 'azx'Der normalisierte Zeichenfolge (Hash) repräsentiert die Schichtmuster sodass Zeichenfolgen mit demselben Muster denselben Hash haben. Wir verwenden eine Hash-Map, um diese Hashes zu verfolgen und sie entsprechenden Gruppen zuzuordnen. Für jede Zeichenfolge berechnen wir einen Hash und verwenden ihn, um entweder eine neue Gruppe zu erstellen oder die Zeichenfolge in einem einzigen Durchlauf zu einer vorhandenen Gruppe hinzuzufügen.
// 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 ( ' ' )));
Ausgabe
acd dfg wyz yab mop bdfh moqs a x
Zeitkomplexität: O(n*k) wobei n die Länge des String-Arrays und k die maximale Länge eines Strings im String-Array ist.
Hilfsraum: O(n*k) Im schlimmsten Fall könnten wir für jeden Eingabestring jeweils n verschiedene Hash-Strings generieren. Wir haben also n verschiedene Einträge in der Hash-Map, jeder mit der Länge k oder weniger.
