Question

804. Unique Morse Code Words

中文文档

Description

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows:

• 'a' maps to ".-",
• 'b' maps to "-...",
• 'c' maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Given an array of strings words where each word can be written as a concatenation of the Morse code of each letter.

• For example, "cab" can be written as "-.-..--...", which is the concatenation of "-.-.", ".-", and "-...". We will call such a concatenation the transformation of a word.

Return _the number of different transformations among all words we have_.

 

Example 1:

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 "--...--.".

Example 2:

Input: words = ["a"]
Output: 1

 

Constraints:

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

Solutions

Solution 1

class Solution:
  def uniqueMorseRepresentations(self, words: List[str]) -> int:
    codes = [
      ".-",
      "-...",
      "-.-.",
      "-..",
      ".",
      "..-.",
      "--.",
      "....",
      "..",
      ".---",
      "-.-",
      ".-..",
      "--",
      "-.",
      "---",
      ".--.",
      "--.-",
      ".-.",
      "...",
      "-",
      "..-",
      "...-",
      ".--",
      "-..-",
      "-.--",
      "--..",
    ]
    s = {''.join([codes[ord(c) - ord('a')] for c in word]) for word in words}
    return len(s)

class Solution {
  public int uniqueMorseRepresentations(String[] words) {
    String[] codes = new String[] {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....",
      "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
      "..-", "...-", ".--", "-..-", "-.--", "--.."};
    Set<String> s = new HashSet<>();
    for (String word : words) {
      StringBuilder t = new StringBuilder();
      for (char c : word.toCharArray()) {
        t.append(codes[c - 'a']);
      }
      s.add(t.toString());
    }
    return s.size();
  }
}

class Solution {
public:
  int uniqueMorseRepresentations(vector<string>& words) {
    vector<string> codes = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.",
      "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."};
    unordered_set<string> s;
    for (auto& word : words) {
      string t;
      for (char& c : word) t += codes[c - 'a'];
      s.insert(t);
    }
    return s.size();
  }
};

func uniqueMorseRepresentations(words []string) int {
  codes := []string{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.",
    "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}
  s := make(map[string]bool)
  for _, word := range words {
    t := &strings.Builder{}
    for _, c := range word {
      t.WriteString(codes[c-'a'])
    }
    s[t.String()] = true
  }
  return len(s)
}

const codes = [
  '.-',
  '-...',
  '-.-.',
  '-..',
  '.',
  '..-.',
  '--.',
  '....',
  '..',
  '.---',
  '-.-',
  '.-..',
  '--',
  '-.',
  '---',
  '.--.',
  '--.-',
  '.-.',
  '...',
  '-',
  '..-',
  '...-',
  '.--',
  '-..-',
  '-.--',
  '--..',
];

function uniqueMorseRepresentations(words: string[]): number {
  return new Set(
    words.map(word => {
      return word
        .split('')
        .map(c => codes[c.charCodeAt(0) - 'a'.charCodeAt(0)])
        .join('');
    }),
  ).size;
}

use std::collections::HashSet;
impl Solution {
  pub fn unique_morse_representations(words: Vec<String>) -> i32 {
    const codes: [&str; 26] = [
      ".-",
      "-...",
      "-.-.",
      "-..",
      ".",
      "..-.",
      "--.",
      "....",
      "..",
      ".---",
      "-.-",
      ".-..",
      "--",
      "-.",
      "---",
      ".--.",
      "--.-",
      ".-.",
      "...",
      "-",
      "..-",
      "...-",
      ".--",
      "-..-",
      "-.--",
      "--..",
    ];
    words
      .iter()
      .map(|word| {
        word.as_bytes()
          .iter()
          .map(|v| codes[(v - b'a') as usize])
          .collect::<String>()
      })
      .collect::<HashSet<String>>()
      .len() as i32
  }
}