给定一个小写字符串数组，任务是找到不同的字符串数。如果对一个字符串应用以下操作时，无法形成第二个字符串，则两个字符串是不同的。
null
- 奇数索引上的一个字符只能与奇数索引上的另一个字符交换。
- 偶数索引中的一个字符只能与偶数索引中的另一个字符交换。
例如：
Input : arr[] = {"abcd", "cbad", "bacd"}Output : 2The 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. 简单解决方案 就是运行两个循环。外部循环选择一个字符串，内部循环检查是否有以前的字符串可以通过允许的转换转换为当前字符串。这个解决方案需要O（n 2. m） 时间，其中n是字符串数，m是任何字符串中的最大字符数。
一 有效解决方案 为每个输入字符串生成一个编码字符串。编码后的字符具有由分隔符分隔的奇偶定位字符数。如果两个字符串的编码字符串相同，则认为它们是相同的，否则就不一样。一旦我们有了编码字符串的方法，问题就简化为计算不同的编码字符串。这是一个典型的哈希问题。我们创建一个散列集，并逐个存储字符串的编码。如果编码已经存在，我们将忽略该字符串。否则，我们将编码存储在散列中，并增加不同字符串的计数。
C++
#include<bits/stdc++.h> 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]; // 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 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()+1]; strcpy (char_array, input[i].c_str()); if (s.find(encodeString(char_array, input[i].length()+1)) == s.end()) { s.insert(encodeString(char_array,input[i].length()+1)); countDist++; } } return countDist; } // Driver code int main() { string input[] = { "abcd" , "acbd" , "adcb" , "cdba" , "bcda" , "badc" }; int n = sizeof (input)/ sizeof (input[0]); cout << countDistinct(input, n) << "" ; } // This code is contributed by NishaBharti. |
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 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 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 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> |
输出
4
本文由 kp93 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
