Cuente distintas strings posibles reemplazando cada carácter por su código Morse

Dada una array de strings arr[] , la tarea es contar el número de strings distintas que se pueden generar a partir de la array dada reemplazando cada carácter de las strings por su código Morse . A continuación se muestra el código Morse de todos los alfabetos en minúsculas:

Ejemplos:

Entrada: arr[] ={“gig”, “zeg”, “gin”, “msn”}
Salida: 2
Explicación: 
Reemplazar cada carácter de las strings de la array dada por su código Morse: 
gig = “–…–. ” 
zeg = “–…–.” 
ginebra = “–…-.” 
msn = “–…-.” 
El código Morse de las strings «gig» y «zeg» son iguales. 
El código Morse de las strings «gin» y «msn» son iguales. 
Por lo tanto, el recuento total de elementos distintos de la string dada al reemplazar los caracteres por su código Morse es igual a 2. 
 

Entrada: arr[] = {“geeks”, “for”, “geeks”}
Salida: 2

Enfoque: siga los pasos a continuación para resolver el problema:

• Inicialice una array , diga morseCode[] para almacenar el código Morse de todos los caracteres en minúsculas.
• Cree un conjunto , digamos st para almacenar distintos elementos de la array reemplazando cada carácter por su código Morse.
• Atraviese la array e inserte el código Morse de la string de la array en st .
• Finalmente, imprima el conteo de elementos presentes en st .

A continuación se muestra la implementación del enfoque anterior.

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count unique array elements
// by replacing each character by its Morse code
int uniqueMorseRep(vector<string>& arr)
{
 
    // Stores Morse code of all
    // lowercase characters
    vector<string> morseCode
        = {
            ".-", "-...", "-.-.",
            "-..", ".", "..-.", "--.",
            "....", "..", ".---", "-.-",
            ".-..", "--", "-.", "---",
            ".--.", "--.-", ".-.", "...",
            "-", "..-", "...-", ".--",
            "-..-", "-.--", "--.."
          };
 
    // Stores distinct elements of string by
    // replacing each character by Morse code
    set<string> st;
 
    // Stores length of arr[] array
    int N = arr.size();
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Stores the Morse code
        // of arr[i]
        string temp = "";
 
        // Stores length of
        // current string
        int M = arr[i].length();
 
        for (int j = 0; j < M; j++) {
 
            // Update temp
            temp += morseCode[arr[i][j] - 'a'];
        }
 
        // Insert temp into st
        st.insert(temp);
    }
 
    // Return count of elements
    // in the set
    return st.size();
}
 
// Driver code
int main()
{
    vector<string> arr = { "gig", "zeg",
                           "gin", "msn" };
    cout << uniqueMorseRep(arr) << endl;
}

// Java program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to count unique
// array elements by replacing
// each character by its Morse code
static int uniqueMorseRep(String[] arr)
{
  // Stores Morse code of all
  // lowercase characters
  String []morseCode = {".-", "-...", "-.-.",
                        "-..", ".", "..-.", "--.",
                        "....", "..", ".---", "-.-",
                        ".-..", "--", "-.", "---",
                        ".--.", "--.-", ".-.", "...",
                        "-", "..-", "...-", ".--",
                        "-..-", "-.--", "--.."};
 
  // Stores distinct elements of
  // String by replacing each
  // character by Morse code
  HashSet<String> st = new HashSet<>();
 
  // Stores length of arr[] array
  int N = arr.length;
 
  // Traverse the array
  for (int i = 0; i < N; i++)
  {
    // Stores the Morse code
    // of arr[i]
    String temp = "";
 
    // Stores length of
    // current String
    int M = arr[i].length();
 
    for (int j = 0; j < M; j++)
    {
      // Update temp
      temp += morseCode[arr[i].charAt(j) - 'a'];
    }
 
    // Insert temp into st
    st.add(temp);
  }
 
  // Return count of elements
  // in the set
  return st.size();
}
 
// Driver code
public static void main(String[] args)
{
  String[] arr = {"gig", "zeg",
                  "gin", "msn"};
  System.out.print(uniqueMorseRep(arr) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to implement
# the above approach
 
# Function to count unique
# array elements by replacing
# each character by its Morse
# code
def uniqueMorseRep(arr):
   
    # Stores Morse code of
    # all lowercase characters
    morseCode = [".-", "-...", "-.-.",
                 "-..", ".", "..-.",
                 "--.", "....", "..",
                 ".---", "-.-", ".-..",
                 "--", "-.", "---", ".--.",
                 "--.-", ".-.", "...", "-",
                 "..-", "...-", ".--", "-..-",
                 "-.--", "--.."];
 
    # Stores distinct elements of
    # String by replacing each
    # character by Morse code
    st = set();
 
    # Stores length of arr array
    N = len(arr);
 
    # Traverse the array
    for i in range(N):
       
        # Stores the Morse code
        # of arr[i]
        temp = "";
 
        # Stores length of
        # current String
        M = len(arr[i]);
 
        for j in range(M):
           
            # Update temp
            temp += morseCode[ord(arr[i][j]) -
                              ord('a')];
 
        # Insert temp into st
        st.add(temp);
 
    # Return count of elements
    # in the set
    return len(st);
 
# Driver code
if __name__ == '__main__':
   
    arr = ["gig", "zeg",
           "gin", "msn"];
    print(uniqueMorseRep(arr) , "");
 
# This code is contributed by 29AjayKumar

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to count unique
// array elements by replacing
// each character by its Morse code
static int uniqueMorseRep(String[] arr)
{
  // Stores Morse code of all
  // lowercase characters
  String []morseCode = {".-", "-...", "-.-.",
                        "-..", ".", "..-.", "--.",
                        "....", "..", ".---", "-.-",
                        ".-..", "--", "-.", "---",
                        ".--.", "--.-", ".-.", "...",
                        "-", "..-", "...-", ".--",
                        "-..-", "-.--", "--.."};
 
  // Stores distinct elements of
  // String by replacing each
  // character by Morse code
  HashSet<String> st = new HashSet<String>();
 
  // Stores length of []arr array
  int N = arr.Length;
 
  // Traverse the array
  for (int i = 0; i < N; i++)
  {
    // Stores the Morse code
    // of arr[i]
    String temp = "";
 
    // Stores length of
    // current String
    int M = arr[i].Length;
 
    for (int j = 0; j < M; j++)
    {
      // Update temp
      temp += morseCode[arr[i][j] - 'a'];
    }
 
    // Insert temp into st
    st.Add(temp);
  }
 
  // Return count of elements
  // in the set
  return st.Count;
}
 
// Driver code
public static void Main(String[] args)
{
  String[] arr = {"gig", "zeg",
                  "gin", "msn"};
  Console.Write(uniqueMorseRep(arr) + "\n");
}
}
 
// This code is contributed by gauravrajput1

<script>
 
// Javascript program to implement
// the above approach
 
// Function to count unique array elements
// by replacing each character by its Morse code
function uniqueMorseRep(arr)
{
 
    // Stores Morse code of all
    // lowercase characters
    var morseCode
        = [
            ".-", "-...", "-.-.",
            "-..", ".", "..-.", "--.",
            "....", "..", ".---", "-.-",
            ".-..", "--", "-.", "---",
            ".--.", "--.-", ".-.", "...",
            "-", "..-", "...-", ".--",
            "-..-", "-.--", "--.."];
 
    // Stores distinct elements of string by
    // replacing each character by Morse code
    var st = new Set();
 
    // Stores length of arr[] array
    var N = arr.length;
 
    // Traverse the array
    for (var i = 0; i < N; i++) {
 
        // Stores the Morse code
        // of arr[i]
        var temp = "";
 
        // Stores length of
        // current string
        var M = arr[i].length;
 
        for (var j = 0; j < M; j++) {
 
            // Update temp
            temp += morseCode[arr[i][j].charCodeAt(0) - 'a'.charCodeAt(0)];
        }
 
        // Insert temp into st
        st.add(temp);
    }
 
    // Return count of elements
    // in the set
    return st.size;
}
 
// Driver code
var arr = ["gig", "zeg",
                       "gin", "msn"];
document.write( uniqueMorseRep(arr));
 
</script>

2

Complejidad de tiempo: O(N×M) , donde N es el tamaño de la array y M es la longitud de una palabra.
Espacio Auxiliar: O(N)