Șiruri distincte cu modificări par și impare permise
Având în vedere o serie de șiruri de caractere mici, sarcina este de a găsi numărul de șiruri care sunt distincte. Două șiruri sunt distincte dacă la aplicarea următoarelor operații pe un șir nu se poate forma al doilea șir.
- Un caracter de pe indexul impar poate fi schimbat doar cu un alt caracter de pe indexul impar.
- Un caracter pe indexul par poate fi schimbat cu un alt caracter numai pe indexul par.
Exemple:
Input : arr[] = {'abcd' 'cbad' 'bacd'} Output : 2 The 2nd string can be converted to the 1st by swapping the first and third characters. So there are 2 distinct strings as the third string cannot be converted to the first. Input : arr[] = {'abc' 'cba'} Output : 1 O solutie simpla este să rulezi două bucle. Bucla exterioară alege un șir, iar bucla interioară verifică dacă există un șir anterior care poate fi convertit într-un șir curent făcând transformări permise. Această soluție necesită O(n 2 m) timp unde n este numărul de șiruri și m este numărul maxim de caractere din orice șir.
Un solutie eficienta generează un șir codificat pentru fiecare șir de intrare. Codul are numărătoare de caractere poziționate pare și impare separate printr-un separator. Două șiruri sunt considerate identice dacă șirurile lor codificate sunt aceleași, altfel nu. Odată ce avem o modalitate de a codifica șiruri, problema se reduce la numărarea șirurilor distincte codificate. Aceasta este o problemă tipică de hashing. Creăm un set hash și stocăm una câte una codificări de șiruri. Dacă o codificare există deja, ignorăm șirul. În caz contrar, stocăm codificarea în hash și incrementăm numărul de șiruri distincte.
Implementare:
C++ #include using namespace std ; int MAX_CHAR = 26 ; string encodeString ( char str [] int m ) { // hashEven stores the count of even indexed character // for each string hashOdd stores the count of odd // indexed characters for each string int hashEven [ MAX_CHAR ]; int hashOdd [ MAX_CHAR ]; memset ( hashEven 0 sizeof ( hashEven )); memset ( hashOdd 0 sizeof ( hashOdd )); // creating hash for each string for ( int i = 0 ; i < m ; i ++ ) { char c = str [ i ]; if (( i & 1 ) != 0 ) // If index of current character is odd hashOdd [ c - 'a' ] ++ ; else hashEven [ c - 'a' ] ++ ; } // For every character from 'a' to 'z' we store its // count at even position followed by a separator // followed by count at odd position. string encoding = '' ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { encoding += ( hashEven [ i ]); encoding += ( '-' ); encoding += ( hashOdd [ i ]); encoding += ( '-' ); } return encoding ; } // This function basically uses a hashing based set to // store strings which are distinct according // to criteria given in question. int countDistinct ( string input [] int n ) { int countDist = 0 ; // Initialize result // Create an empty set and store all distinct // strings in it. set < string > s ; for ( int i = 0 ; i < n ; i ++ ) { // If this encoding appears first time increment // count of distinct encodings. char char_array [ input [ i ]. length ()]; strcpy ( char_array input [ i ]. c_str ()); if ( s . find ( encodeString ( char_array input [ i ]. length ())) == s . end ()) { s . insert ( encodeString ( char_array input [ i ]. length ())); countDist ++ ; } } return countDist ; } int main () { string input [] = { 'abcd' 'acbd' 'adcb' 'cdba' 'bcda' 'badc' }; int n = sizeof ( input ) / sizeof ( input [ 0 ]); cout < < countDistinct ( input n ) < < ' n ' ; } // This code is contributed by Harshit Sharma.
Java // Java program to count distinct strings with // even odd swapping allowed. import java.util.HashSet ; import java.util.Set ; class GFG { static int MAX_CHAR = 26 ; static String encodeString ( char [] str ) { // hashEven stores the count of even indexed character // for each string hashOdd stores the count of odd // indexed characters for each string int hashEven [] = new int [ MAX_CHAR ] ; int hashOdd [] = new int [ MAX_CHAR ] ; // creating hash for each string for ( int i = 0 ; i < str . length ; i ++ ) { char c = str [ i ] ; if (( i & 1 ) != 0 ) // If index of current character is odd hashOdd [ c - 'a' ]++ ; else hashEven [ c - 'a' ]++ ; } // For every character from 'a' to 'z' we store its // count at even position followed by a separator // followed by count at odd position. String encoding = '' ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { encoding += ( hashEven [ i ] ); encoding += ( '-' ); encoding += ( hashOdd [ i ] ); encoding += ( '-' ); } return encoding ; } // This function basically uses a hashing based set to // store strings which are distinct according // to criteria given in question. static int countDistinct ( String input [] int n ) { int countDist = 0 ; // Initialize result // Create an empty set and store all distinct // strings in it. Set < String > s = new HashSet <> (); for ( int i = 0 ; i < n ; i ++ ) { // If this encoding appears first time increment // count of distinct encodings. if ( ! s . contains ( encodeString ( input [ i ] . toCharArray ()))) { s . add ( encodeString ( input [ i ] . toCharArray ())); countDist ++ ; } } return countDist ; } public static void main ( String [] args ) { String input [] = { 'abcd' 'acbd' 'adcb' 'cdba' 'bcda' 'badc' }; int n = input . length ; System . out . println ( countDistinct ( input n )); } }
Python3 # Python3 program to count distinct strings with # even odd swapping allowed. MAX_CHAR = 26 # Returns encoding of string that can be used # for hashing. The idea is to return same encoding # for strings which can become same after swapping # a even positioned character with other even characters # OR swapping an odd character with other odd characters. def encodeString ( string ): # hashEven stores the count of even indexed character # for each string hashOdd stores the count of odd # indexed characters for each string hashEven = [ 0 ] * MAX_CHAR hashOdd = [ 0 ] * MAX_CHAR # creating hash for each string for i in range ( len ( string )): c = string [ i ] if i & 1 : # If index of current character is odd hashOdd [ ord ( c ) - ord ( 'a' )] += 1 else : hashEven [ ord ( c ) - ord ( 'a' )] += 1 # For every character from 'a' to 'z' we store its # count at even position followed by a separator # followed by count at odd position. encoding = '' for i in range ( MAX_CHAR ): encoding += str ( hashEven [ i ]) encoding += str ( '-' ) encoding += str ( hashOdd [ i ]) encoding += str ( '-' ) return encoding # This function basically uses a hashing based set to # store strings which are distinct according # to criteria given in question. def countDistinct ( input n ): countDist = 0 # Initialize result # Create an empty set and store all distinct # strings in it. s = set () for i in range ( n ): # If this encoding appears first time increment # count of distinct encodings. if encodeString ( input [ i ]) not in s : s . add ( encodeString ( input [ i ])) countDist += 1 return countDist # Driver Code if __name__ == '__main__' : input = [ 'abcd' 'acbd' 'adcb' 'cdba' 'bcda' 'badc' ] n = len ( input ) print ( countDistinct ( input n )) # This code is contributed by # sanjeev2552
C# // C# program to count distinct strings with // even odd swapping allowed. using System ; using System.Collections.Generic ; class GFG { static int MAX_CHAR = 26 ; static String encodeString ( char [] str ) { // hashEven stores the count of even // indexed character for each string // hashOdd stores the count of odd // indexed characters for each string int [] hashEven = new int [ MAX_CHAR ]; int [] hashOdd = new int [ MAX_CHAR ]; // creating hash for each string for ( int i = 0 ; i < str . Length ; i ++ ) { char m = str [ i ]; // If index of current character is odd if (( i & 1 ) != 0 ) hashOdd [ m - 'a' ] ++ ; else hashEven [ m - 'a' ] ++ ; } // For every character from 'a' to 'z' // we store its count at even position // followed by a separator // followed by count at odd position. String encoding = '' ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { encoding += ( hashEven [ i ]); encoding += ( '-' ); encoding += ( hashOdd [ i ]); encoding += ( '-' ); } return encoding ; } // This function basically uses a hashing based set // to store strings which are distinct according // to criteria given in question. static int countDistinct ( String [] input int n ) { int countDist = 0 ; // Initialize result // Create an empty set and store all distinct // strings in it. HashSet < String > s = new HashSet < String > (); for ( int i = 0 ; i < n ; i ++ ) { // If this encoding appears first time // increment count of distinct encodings. if ( ! s . Contains ( encodeString ( input [ i ]. ToCharArray ()))) { s . Add ( encodeString ( input [ i ]. ToCharArray ())); countDist ++ ; } } return countDist ; } // Driver Code public static void Main ( String [] args ) { String [] input = { 'abcd' 'acbd' 'adcb' 'cdba' 'bcda' 'badc' }; int n = input . Length ; Console . WriteLine ( countDistinct ( input n )); } } // This code is contributed by 29AjayKumar
JavaScript < script > // Javascript program to count distinct strings with // even odd swapping allowed let MAX_CHAR = 26 ; function encodeString ( str ) { // hashEven stores the count of even indexed character // for each string hashOdd stores the count of odd // indexed characters for each string let hashEven = Array ( MAX_CHAR ). fill ( 0 ); let hashOdd = Array ( MAX_CHAR ). fill ( 0 ); // creating hash for each string for ( let i = 0 ; i < str . length ; i ++ ) { let c = str [ i ]; if (( i & 1 ) != 0 ) // If index of current character is odd hashOdd [ c . charCodeAt () - 'a' . charCodeAt ()] ++ ; else hashEven [ c . charCodeAt () - 'a' . charCodeAt ()] ++ ; } // For every character from 'a' to 'z' we store its // count at even position followed by a separator // followed by count at odd position. let encoding = '' ; for ( let i = 0 ; i < MAX_CHAR ; i ++ ) { encoding += ( hashEven [ i ]); encoding += ( '-' ); encoding += ( hashOdd [ i ]); encoding += ( '-' ); } return encoding ; } // This function basically uses a hashing based set to // store strings which are distinct according // to criteria given in question. function countDistinct ( input n ) { let countDist = 0 ; // Initialize result // Create an empty set and store all distinct // strings in it. let s = new Set (); for ( let i = 0 ; i < n ; i ++ ) { // If this encoding appears first time increment // count of distinct encodings. if ( ! s . has ( encodeString ( input [ i ]. split ( '' )))) { s . add ( encodeString ( input [ i ]. split ( '' ))); countDist ++ ; } } return countDist ; } // Driver program let input = [ 'abcd' 'acbd' 'adcb' 'cdba' 'bcda' 'badc' ]; let n = input . length ; document . write ( countDistinct ( input n )); < /script>
Ieșire
4
Complexitatea timpului : Pe)
Spațiu auxiliar: O(1)
Creați un test
