奇数および偶数の変更が許可される個別の文字列

小文字の文字列の配列が与えられた場合、タスクは、異なる文字列の数を見つけることです。 1 つの文字列に次の操作を適用しても 2 番目の文字列を形成できない場合、2 つの文字列は別個のものになります。

奇数インデックス上の文字は、奇数インデックス上の別の文字とのみ交換できます。
偶数インデックス上の文字は、偶数インデックス上の別の文字とのみ交換できます。

例:

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

あ 簡単な解決策 2 つのループを実行することです。外側のループは文字列を選択し、内側のループは、許可された変換を実行することで現在の文字列に変換できる以前の文字列が存在するかどうかを確認します。この解決策には O(n²m) 時間。n は文字列の数、m は文字列内の最大文字数です。

アン 効率的なソリューション すべての入力文字列に対してエンコードされた文字列を生成します。エンコードされたものには、区切り文字で区切られた偶数位置と奇数位置の文字のカウントが含まれます。 2 つの文字列は、エンコードされた文字列が同じである場合は同じとみなされますが、そうでない場合は同じではありません。文字列をエンコードする方法が確立されると、問題はエンコードされた個別の文字列をカウントすることになります。これはハッシュの典型的な問題です。ハッシュセットを作成し、文字列のエンコーディングを 1 つずつ保存します。エンコーディングがすでに存在する場合、文字列は無視されます。それ以外の場合は、エンコードをハッシュに保存し、個別の文字列のカウントをインクリメントします。

実装：

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(hashEven0sizeof(hashEven));  memset(hashOdd0sizeof(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_arrayinput[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# 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>

出力

時間計算量 : の上）
補助スペース : O(1)

クイズの作成