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.

Submitted Code

class Solution(object):
    def uniqueMorseRepresentations(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        transformations = []
        codes = {
            "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": "--.."
        }

        for word in words:
            t = ""
            for ch in word:
                t += codes[ch]
            if t not in transformations:
                transformations.append(t)
        
        return len(transformations)

Runtime: 0 ms | Beats 100.00%
Memory: 12.42 MB | Beats 48.53%

문제 설명에 있는 모스부호 리스트로 해시 테이블을 만들었다.

Other Solutions

1st

    def uniqueMorseRepresentations(self, words):
        d = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--",
             "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
        return len({''.join(d[ord(i) - ord('a')] for i in w) for w in words})

time complexity: 𝑂(𝑛*𝑚)
space complexity: 𝑂(𝑛*𝑚)

알파벳의 아스키코드값을 이용하면 해시 테이블을 따로 만들지 않아도 모스부호 리스트만으로 풀 수 있다.