Különálló karakterláncok páratlan és páros változtatásokkal megengedettek
Adott egy sor kisbetűs karakterláncot, a feladat az, hogy megkeressük a különböző karakterláncok számát. Két karakterlánc különbözik, ha a következő műveleteket egy karakterláncra alkalmazva a második karakterláncot nem lehet létrehozni.
- A páratlan indexben szereplő karakter csak a páratlan indexen lévő másik karakterrel cserélhető fel.
- A páros indexen lévő karaktert csak a páros indexen lehet felcserélni egy másik karakterrel.
Példák:
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 A egyszerű megoldás két hurok futtatása. A külső hurok kiválaszt egy karakterláncot, a belső pedig ellenőrzi, hogy van-e korábban olyan karakterlánc, amely engedélyezett átalakításokkal konvertálható aktuális karakterláncsá. Ehhez a megoldáshoz O(n 2 m) idő ahol n a karakterláncok száma, m pedig a karakterek maximális száma bármely karakterláncban.
An hatékony megoldás minden bemeneti karakterlánchoz kódolt karakterláncot generál. A kódolt páros és páratlan helyzetű karaktereket tartalmaz elválasztóval elválasztva. Két karakterlánc azonosnak tekintendő, ha a kódolt karakterláncuk azonos, akkor egyébként nem. Amint módunk van a karakterláncok kódolására, a probléma a különböző kódolt karakterláncok megszámlálására redukálódik. Ez a hashelés tipikus problémája. Létrehozunk egy hash készletet, és egyenként tároljuk a karakterláncok kódolásait. Ha már létezik kódolás, figyelmen kívül hagyjuk a karakterláncot. Ellenkező esetben a kódolást hash-ben tároljuk, és a különböző karakterláncok számát növeljük.
Végrehajtás:
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>
Kimenet
4
Időbeli összetettség : On)
Segédtér: O(1)
Kvíz létrehozása
