그룹 이동 문자열
GfG Practice에서 사용해 보세요. 
산출
문자열 배열(모두 소문자)이 주어지면 그룹의 모든 문자열이 서로 이동된 버전이 되도록 그룹화하는 것이 작업입니다.
두 개의 문자열 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 #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 ( ' ' )));
산출
acd dfg wyz yab mop bdfh moqs a x
시간 복잡도: O(n*k) 여기서 n은 문자열 배열의 길이이고 k는 문자열 배열의 최대 문자열 길이입니다.
보조 공간: O(n*k) 최악의 경우 각 입력 문자열에 대해 각각 n개의 서로 다른 해시 문자열을 생성할 수 있습니다. 그래서 우리는 길이가 k 이하인 해시 맵에 n개의 서로 다른 항목을 얻었습니다.
