Sponsored
Sponsored
We can utilize a HashSet data structure to store the unique transformations. For each word, we can generate its Morse code transformation by replacing each character by its corresponding Morse code. We then add each transformation to the HashSet to automatically handle duplicates. The size of the HashSet at the end gives us the number of unique transformations.
Time Complexity: O(N), where N is the total number of characters across all words.
Space Complexity: O(WL), where W is the number of words and L is the length of the longest word, due to storing transformations.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <stdbool.h>
5
6#define ALPHABET_SIZE 26
7
8char* morseMap[] = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." };
9
10unsigned long hash(char *str) {
11 unsigned long hash = 5381;
12 int c;
13 while ((c = *str++)) {
14 hash = ((hash << 5) + hash) + c;
15 }
16 return hash;
17}
18
19bool checkUnique(char *transformation, unsigned long *hashSet, int size, int *len) {
20 unsigned long hashValue = hash(transformation);
21 for(int i = 0; i < *len; i++) {
22 if(hashSet[i] == hashValue) {
23 return false;
24 }
25 }
26 hashSet[(*len)++] = hashValue;
27 return true;
28}
29
30int uniqueMorseRepresentations(char **words, int wordsSize) {
31 unsigned long *hashSet = (unsigned long *)malloc(wordsSize * sizeof(unsigned long));
32 int uniqueCount = 0;
33
34 for (int i = 0; i < wordsSize; i++) {
35 char transformation[100] = "";
36 char *word = words[i];
37 while (*word) {
38 strcat(transformation, morseMap[*word - 'a']);
39 word++;
40 }
41
42 if (checkUnique(transformation, hashSet, wordsSize, &uniqueCount)) {
43 // Word's transformation is unique
44 }
45 }
46
47 free(hashSet);
48 return uniqueCount;
49}
50
51int main() {
52 char *words[] = {"gin", "zen", "gig", "msg"};
53 int size = sizeof(words) / sizeof(words[0]);
54 printf("%d\n", uniqueMorseRepresentations(words, size));
55 return 0;
56}We use a simple array to act as a HashSet. First, we define the mappings from characters to Morse code. We then iterate through each word, building its Morse code transformation. Each transformation is hashed and compared to our set of seen hashes. If a hash is not seen before, it is added to the array. This method ensures that we only count unique transformations.
In this method, we establish a direct mapping of characters to Morse code using a fixed array index, which simplifies the translation process by utilizing the ASCII value difference between 'a' and the current character. We then use the translated words to populate a set directly, ensuring uniqueness of each transformation.
Time Complexity: O(N^2), due to checking each transformation against existing ones in the list.
Space Complexity: O(WL), where W is the word count and L is the length of the longest word, needed to store transformations.
1
This solution translates each letter directly using its index in the Morse code map. We store each unique transformation in a manual list and check new transformations against existing ones. This is less optimal than using hash sets but demonstrates another way to accomplish the task.