“Offer comes, ask friends to take it! I am participating in the 2022 Spring Recruit Punch card campaign. Click here for more details.”

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 95th day 🎈!
🚀 Algorithm 🚀

🌲 A unique Morse code word

The International Morse code defines a standard encoding for each letter to correspond to a string consisting of a series of dots and dashes, such as:

  • ‘a’ corresponds to “.-“,
  • ‘b’ corresponding “-…” .
  • ‘c’ corresponds to “-.. -.”, and so on.

For convenience, the list of Morse passwords for all 26 English letters is as follows:

["-"."-..."."-. -."."-..".".".".. -."."-."."..."."..".". -- -"."-.-".". -.."."--"."-."."-".".--."."-- -".."-."."..."."-".".. -"."... -"."--"."-.. -"."- -"."-.."]
Copy the code

You are given an array of strings called words. Each word can be written as a combination of Morse passwords for each letter.

  • For example, “cab” can be written as “-.. -.. -…” , (i.e.” -… -.” + “.-” + “-…” String combination). We call this linking process word translation.

Translate all words in words and return the number of different word translations.

Example 1:

Enter: words = ["gin"."zen"."gig"."msg"] output:2The words are translated as follows:"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "-... -."
"msg" -> "-... -."A total of2Different translations,"--...-." 和 "-... -.".
Copy the code

Example 2:

Enter: words = ["a"] output:1
Copy the code

Tip:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 12
  • Words [I] consists of lowercase English letters

🌻C# method: violence method

Just write the Morse code for all the letters into the dictionary, and then the word can be translated into the Morse code.

The only difficulty is having the patience to type 26 letters and 26 passwords into the dictionary.

Code:

public class Solution
{
    public int UniqueMorseRepresentations(string[] words)
    {
        Dictionary<char.string> Dic = new Dictionary<char.string> () {{'a'."-"}, {'b'."-..."}, {'c'."-. -."}, {'d'."-.."}, {'e'."."}, {'f'.".. -."}, {'g'."-."}, {'h'."..."},
         {'i'.".."}, {'j'.". -- -"}, {'k'."-.-"}, {'l'.". -.."}, {'m'."--"}, {'n'."-."}, {'o'."-"}, {'p'.".--."},
         {'q'."-- -".}, {'r'."-."}, {'s'."..."}, {'t'."-"}, {'u'.".. -"}, {'v'."... -"}, {'w'."--"}, {'x'."-.. -"},
         {'y'."- -"}, {'z'."-.."}};// Enter the Morse password for each of the 26 letters one by one. Key is the letter and value is the password.

        StringBuilder SB = new StringBuilder();// Create a new StringBuilder. This is a faster way to change strings often, because each letter of the string needs to be changed.
        Dictionary<String, int> Dic2 = new Dictionary<string.int> ();// This dictionary is used to store different Morse passwords.
       

        foreach(string i in words)// Walk through all the words in words.
        {
            for(int j = 0; j < i.Length; j++)// Iterate over the letters of the word
            {
                // Connect the Morse code for each letter.
                SB.Append(Dic[  i[j]Dic[I [j]] = Dic[I [j] = Dic[I [j] = Dic]); }//↓ After traversing a word, if the Morse password is not stored in Dic2, add it and set value to 1 (this is arbitrary, as long as you know the password exists).
            if(! Dic2.ContainsKey(SB.ToString())) { Dic2.Add(SB.ToString(),1);
            }

         SB.Clear();// Finally, empty the StringBuilder because it will be needed to iterate through the next string of words.

        }

        return Dic2.Count;// Return the number of Dic2, which represents the number of unduplicated passwords.}}//leetcode-cn.com/problems/unique-morse-code-words/solution/bao-li-cha-zi-dian-cha-jiu-wan-shi-liao-by-huang-g/
Copy the code

The execution result

By execution time:88Ms, in all C# beat 25.50% of users in submissionMemory consumption:35.4MB, in all C# beat 29.90% of users in submission
Copy the code

🌻Java method: hash collection

We convert each word in the array Word into Morse code

The final answer is the number of elements in the HashSet.

Code:

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] MORSE = new String[]{"-"."-..."."-. -."."-..".".".".. -."."-."."..."."..".". -- -"."-.-".". -.."."--"."-."."-".".--."."-- -".."-."."..."."-".".. -"."... -"."--"."-.. -"."- -"."-.."};

        Set<String> seen = new HashSet();
        for (String word: words) {
            StringBuilder code = new StringBuilder();
            for (char c: word.toCharArray())
                code.append(MORSE[c - 'a']);
            seen.add(code.toString());
        }

        returnseen.size(); }}Copy the code

The execution result

By execution time:1Ms, beat out all Java commits100.00% user memory consumption:36.4MB, beat out all Java commits40.00% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1) 
Copy the code

💬 summary

  • Today is the ninety-fifth day of clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!