문자열 배열(모두 소문자)이 주어지면 그룹의 모든 문자열이 서로 이동된 버전이 되도록 그룹화하는 것이 작업입니다.
csma와 csma CD
두 개의 문자열 s1 그리고 s2 다음 조건이 충족되면 시프트된 것으로 불립니다.
- s1.길이 는 다음과 같다 s2.길이
- s1[i] 는 다음과 같다 s2[i] + 중 1개 모두에 대해<= i <= s1.length for a 끊임없는 정수 m. s2[i] + m > 'z'인 경우 'a'에서 시작하거나 s2[i] + m인 경우 순환적인 이동을 고려하십시오.< 'a' then start from 'z'.
예:
입력: arr[] = ['acd' 'dfg' 'wyz' 'yab' 'mop' 'bdfh' 'a' 'x' 'moqs']
산출: [ ['acd' 'dfg' 'wyz' 'yab' 'mop'] ['bdfh' 'moqs'] ['a' 'x'] ]
설명: 이동된 모든 문자열은 함께 그룹화됩니다.
입력: arr = ['괴짜' 'for' '괴짜']
산출: [['for'] ['괴짜'] ['괴짜']]
접근 방식: 해시 맵 사용
C++아이디어는 독특한 것을 생성하는 것입니다 해시시 각 그룹별로 정규화 문자열. 여기 정규화 필요한 계산을 통해 모든 문자열의 첫 번째 문자를 'a'로 만드는 것을 의미합니다. 교대 모든 문자에 균일하게 적용합니다. 순환 패션 .
예: s = 'dca' 이동 = 'd' - 'a' = 3
정규화된 문자: 'd' - 3 = 'a' 'c' - 3 = 'z' 및 'a' - 3 = 'x'
정규화된 문자열 = 'azx'그만큼 정규화된 문자열 (해시)는 교대 패턴 동일한 패턴을 가진 문자열은 동일한 해시를 갖습니다. 우리는 해시 맵을 사용하여 이러한 해시를 추적하고 해당 그룹에 매핑합니다. 각 문자열에 대해 해시를 계산하고 이를 사용하여 단일 순회로 새 그룹을 만들거나 기존 그룹에 문자열을 추가합니다.
// 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(' ')));
산출
acd dfg wyz yab mop bdfh moqs a x
시간 복잡도: O(n*k) 여기서 n은 문자열 배열의 길이이고 k는 문자열 배열의 최대 문자열 길이입니다.
보조 공간: O(n*k) 최악의 경우 각 입력 문자열에 대해 각각 n개의 서로 다른 해시 문자열을 생성할 수 있습니다. 그래서 우리는 길이가 k 이하인 해시 맵에 n개의 서로 다른 항목을 얻었습니다.
배우 레카