Search for a command to run...
A C++ solution to Leetcode 804. Unique Morse Code Words using mapping and std::unordered_set to keep track of unique representations.
Hi! My name is Nhut Nguyen. I am a software engineer and a writer in Copenhagen, Denmark.
Learn more about me at nhutnguyen.com
No comments yet. Be the first to comment.
A simple example of using C++ switch
Two dynamic programming techniques to solve Leetcode 120. Triangle. One has space complexity O(n^2). The other is O(n).
An example of using a sliding window approach and an unordered map to track character positions
A simple C++ solution to Leetcode 1695. Maximum Erasure Value using a sliding window approach and prefix sums.
Strategies to avoid them will help you excel in your following technical interview
The problem involves the International Morse Code, which defines a standard way to encode letters with dots and dashes. Each English letter corresponds to a specific sequence in Morse Code, and a full table mapping each letter is provided.
For instance, 'a' is encoded as ".-", 'b' as "-...", and so on.
The full table for the 26 letters of the English alphabet is given below:
[".-", "-...", "-.-.", "-..", ".", "..-.", "--.",
"....", "..", ".---", "-.-", ".-..", "--", "-.",
"---", ".--.", "--.-", ".-.", "...", "-", "..-",
"...-", ".--", "-..-", "-.--", "--.."]
You are given an array of strings named words, where each word can be represented as a concatenation of the Morse code for each of its letters. For example, the word "cab" can be represented as "-.-..--...", which is the concatenation of "-.-.", ".-", and "-...". This concatenated Morse code representation is referred to as the "transformation" of a word.
Your task is to count the number of different transformations that can be obtained from all the words in the given array.
Input: words = ["gin","zen","gig","msg"]
Output: 2
Explanation: The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
There are 2 different transformations: "--...-." and "--...--.".
Input: words = ["a"]
Output: 1
1 <= words.length <= 100.
1 <= words[i].length <= 12.
words[i] consists of lowercase English letters.
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int uniqueMorseRepresentations(vector<string>& words)
{
vector<string> morse{
".-", "-...", "-.-.", "-..", ".", "..-.", "--.",
"....", "..", ".---", "-.-", ".-..", "--", "-.",
"---", ".--.", "--.-", ".-.", "...", "-", "..-",
"...-", ".--", "-..-", "-.--", "--.."
};
unordered_set<string> transformations;
for (string& w : words)
{
string s{""};
for (char& c : w)
{
s += morse[c - 'a'];
}
transformations.insert(s);
}
return transformations.size();
}
int main()
{
vector<string> words{"gin","zen","gig","msg"};
cout << uniqueMorseRepresentations(words) << endl;
words = {"a"};
cout << uniqueMorseRepresentations(words) << endl;
}
Output:
2
1
The solution begins with a predefined mapping of lowercase English letters to their corresponding Morse code representations. The Morse code representations are stored in a vector called morse.
An unordered_set<string> transformations is used to store the unique Morse code representations generated from the input words. This set will automatically ensure that only unique representations are stored.
The code iterates through each word in the words vector. For each word, it initializes an empty string s to store the Morse code representation of that word.
It then iterates through each character in the word. For each character c in the word, it appends the corresponding Morse code representation (retrieved from the morse vector) for that character to the s string. The mapping is accessed using morse[c - 'a'].
After constructing the Morse code representation for the current word, it inserts the s string into the transformations set. If s is already present in the set, it will not be added again since sets only allow unique elements.
After processing all the words, the size of the transformations set is returned as the result. The size of the set corresponds to the number of unique Morse code representations generated from the input words.
This solution converts each word into Morse code based on a predefined mapping and uses an unordered set to keep track of unique representations. By inserting each representation into the set, it automatically filters out duplicates. The final result is the size of the set, which represents the number of unique Morse code representations among the input words.
Runtime: O(N*M), where N = words.length and M = words[i].length.
Extra space: O(N).
Thanks for reading! Get my book "10 Classic Coding Challenges" for FREE.