algorithms/leetcode/804-UniqueMorseCodeWords.go at master · freewu/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
package main

// 804. Unique Morse Code Words
// 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.

import "fmt"
import "strings"

func uniqueMorseRepresentations(words []string) int {
    morses := [] string{".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."}
    transformations := make(map[string]bool)
    for _, s := range words {
        transformation := ""
        runes := [] rune(s)
        for _, r := range runes {
            index := r - 'a'
            transformation += morses[index]
        }
        transformations[transformation] = true
    }
    return len(transformations)
}

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

func main() {
    // 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 "--...--.".
    fmt.Println(uniqueMorseRepresentations([]string{"gin","zen","gig","msg"})) // 2
    // Example 2:
    // Input: words = ["a"]
    // Output: 1
    fmt.Println(uniqueMorseRepresentations([]string{"a"})) // 1

    fmt.Println(uniqueMorseRepresentations1([]string{"gin","zen","gig","msg"})) // 2
    fmt.Println(uniqueMorseRepresentations1([]string{"a"})) // 1
}