Ņemot vērā virkņu masīvu (visi mazie burti), uzdevums ir tās grupēt tā, lai visas virknes grupā būtu viena otras nobīdītas versijas.
Divas stīgas s1 un s2 tiek saukti par nobīdītiem, ja ir izpildīti šādi nosacījumi:
- s1.garums ir vienāds ar s2.garums
- s1[i] ir vienāds ar s2[i] + m visiem 1<= i <= s1.length for a nemainīgs vesels skaitlis m. Uzskatiet, ka nobīde ir cikliska, proti, ja s2[i] + m > "z", tad sākas no "a" vai ja s2[i] + m< 'a' then start from 'z'.
Piemēri:
Ievade: arr[] = ['acd' 'dfg' 'wyz' 'yab' 'mop' 'bdfh' 'a' 'x' 'moqs']
Izvade: [ ['acd' 'dfg' 'wyz' 'yab' 'mop'] ['bdfh' 'moqs'] ['a' 'x'] ]
Paskaidrojums: Visas pārvietotās virknes ir sagrupētas kopā.
Ievade: arr = ['geek' 'for' 'geeks']
Izvade: [['for'] ['geek'] ['geeks']]
Pieeja: izmantojot hash karti
C++Ideja ir radīt unikālu hash katrai grupai pa normalizēšana stīgas. Šeit normalizēšana nozīmē katras virknes pirmo rakstzīmi padarīt vienādu ar “a”, aprēķinot nepieciešamo maiņas un vienādi piemērojot to visām rakstzīmēm cikliskā mode .
Piemērs: s = "dca" shifts = "d" - "a" = 3
normalizētas rakstzīmes: "d" - 3 = "a" "c" - 3 = "z" un "a" - 3 = "x"
normalizēta virkne = 'azx'The normalizēta virkne (hash) apzīmē maiņas modelis tā, lai virknēm ar tādu pašu rakstu būtu vienāds jaukums. Mēs izmantojam jaucējkarti, lai izsekotu šīs jaucējzīmes un kartētu tās ar atbilstošām grupām. Katrai virknei mēs aprēķinām jaucējvērtību un izmantojam to, lai izveidotu jaunu grupu vai pievienotu virkni esošai grupai vienā šķērsošanā.
// 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(' ')));
Izvade
acd dfg wyz yab mop bdfh moqs a x
Laika sarežģītība: O(n*k) kur n ir virknes masīva garums un k ir maksimālais virknes garums virkņu masīvā.
Palīgtelpa: O(n*k) sliktākajā gadījumā mēs varētu ģenerēt n dažādas jaucējrindas attiecīgi katrai ievades virknei. Tātad mēs saņēmām n dažādus ierakstus jaucējkartē, kuru garums ir k vai mazāks.