Étant donné un tableau de chaînes (toutes en lettres minuscules), la tâche consiste à les regrouper de telle manière que toutes les chaînes d'un groupe soient des versions décalées les unes des autres.
Deux cordes s1 et s2 sont dits décalés si les conditions suivantes sont satisfaites :
- s1.longueur est égal à s2.longueur
- s1[i] est égal à s2[i] + m pour tous 1<= i <= s1.length for a constante entier m. Considérez le décalage comme cyclique, c'est-à-dire si s2[i] + m > 'z' alors commencez à partir de 'a' ou si s2[i] + m< 'a' then start from 'z'.
Exemples :
Saisir: arr[] = ['acd' 'dfg' 'wyz' 'yab' 'mop' 'bdfh' 'a' 'x' 'moqs']
Sortir: [ ['acd' 'dfg' 'wyz' 'yab' 'mop'] ['bdfh' 'moqs'] ['a' 'x'] ]
Explication: Toutes les chaînes décalées sont regroupées.
Saisir: arr = ['geek' 'pour' 'geeks']
Sortir: [['pour'] ['geek'] ['geeks']]
Approche : utilisation de la carte de hachage
C++L'idée est de générer un unique hacher pour chaque groupe par normaliser les cordes. Ici normaliser signifie rendre le premier caractère de chaque chaîne égal à « a » en calculant le nombre requis changements et l'appliquer uniformément à tous les personnages de mode cyclique .
Exemple : s = 'dca' décale = 'd' - 'a' = 3
caractères normalisés : 'd' - 3 = 'a' 'c' - 3 = 'z' et 'a' - 3 = 'x'
chaîne normalisée = 'azx'Le chaîne normalisée (hachage) représente le modèle de changement de sorte que les chaînes avec le même motif aient le même hachage. Nous utilisons une carte de hachage pour suivre ces hachages et les mapper aux groupes correspondants. Pour chaque chaîne, nous calculons un hachage et l'utilisons pour créer un nouveau groupe ou ajouter la chaîne à un groupe existant en un seul parcours.
// C++ program to print groups of shifted strings // together using Hash Map #include
// 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 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# 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 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(' ')));
Sortir
acd dfg wyz yab mop bdfh moqs a x
Complexité temporelle : O(n*k) où n est la longueur du tableau de chaînes et k est la longueur maximale d'une chaîne dans le tableau de chaînes.
Espace auxiliaire : O(n*k) dans le pire des cas, nous pourrions générer n chaînes de hachage différentes respectivement pour chaque chaîne d'entrée. Nous avons donc n entrées différentes dans la carte de hachage, chacune d'une longueur k ou inférieure.