LeetCode（Map)804. Unique Morse Code Words

Bertha 。 2023-09-24 00:23 52阅读 0赞

# 1.问题 #

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.

# 2. 解题思路 #

## 方法1： ##

> 1.使用Hashset是因为没有重复元素  
> 2.用map存储key（26个字母）和value（ Morse Code ）  
> 3.遍历，将String转为char，map的key字母，获得value，并添加到hashset  
> 4.求hashset的size也就是不重复的元素个数

## 方法2： ##

> 1.使用Hashset是因为没有重复元素  
> 2.遍历数组  
> 1）使用 StringBuilder是可以添加不限长度的元素  
> 2）ASC2码小写字母位置是连续的，所以 ‘字母’-’a’=字母和a的距离，此题就对应morse数组中对应字母的索引,并添加到StringBuilder  
> 3）转换成String添加到hashset  
> 3.求hashset的size也就是不重复的元素个数

## 方法3： ##

理解起来比较简单，可以参考

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int uniqueMorseRepresentations(String[] words) {
        
           Set<String> r= new HashSet<String>();//1.使用Hashset是因为没有重复元素
            Map<Character,String>map = new HashMap<>();//2.用map存储key（26个字母）和value（ Morse Code ）
            String[] morse={
        ".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
            String alp = "";
            for(char i = 'a'; i <= 'z'; ++i){
        
               alp+=i;
            }
            char[]al=alp.toCharArray();
            for(int i=0;i<26;i++){
        
                map.put(al[i],morse[i]);
    
            }
            for(String w:words){
        //3.遍历，将String转为char，map的key字母，获得value，并添加到hashset
                char[] single = w.toCharArray();
                String temp="";
                for(char s: single){
        
                    temp +=map.get(s);
                }
                r.add(temp);
            }
            return  r.size();//4.求hashset的size也就是不重复的元素个数
        }
    }

## 代码2： ##

class Solution {
        
        public int uniqueMorseRepresentations(String[] words) {
        
            String[] tokens = new String[]{
        ".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
            Set<String> set = new HashSet<>();//1.使用Hashset是因为没有重复元素
            for ( String word : words ) {
        //2.遍历数组
                StringBuilder sb = new StringBuilder();//使用 StringBuilder是可以添加不限长度的元素
                for ( int i = 0; i < word.length(); i++ ) {
        //ASC2码小写字母位置是连续的，所以 ‘字母’-’a’=字母和a的距离，此题就对应morse数组中对应字母的索引,并添加到StringBUilder
                    sb.append( tokens[word.charAt(i)-'a'] );//int index=c-'a';sb.append(morseCode[index]);               
    
                }
                set.add( sb.toString() );//转换成String添加到hashset
            }
            return set.size();//3.求hashset的size也就是不重复的元素个数
        }
    }

> 解题思路基本相同

public int uniqueMorseRepresentations(String[] words) {
        
        String[] arr = new String[]{
        ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."};
        Set<String> set = new HashSet<>();
        for (String s : words) {
        
            StringBuilder sb = new StringBuilder();
            for (char ch : s.toCharArray()) sb.append(arr[ch - 'a']);//ASC2码小写字母位置是连续的，所以 ‘字母’-’a’=字母和a的距离，此题就对应morse数组中对应字母的索引
            set.add(sb.toString());
        }
    
        return set.size();
    }

## 代码3： ##

class Solution {
        
        public int uniqueMorseRepresentations(String[] words) {
        
            Map<Character, String> res = new HashMap<>();
            res.put('a', ".-"); res.put('b', "-..."); res.put('c', "-.-."); res.put('d', "-.."); res.put('e', ".");           res.put('f', "..-.");res.put('g', "--."); res.put('h', "...."); res.put('i', ".."); res.put('j', ".---");         res.put('k', "-.-"); res.put('l', ".-.."); res.put('m', "--"); res.put('n', "-."); res.put('o', "---");
            res.put('p', ".--."); res.put('q', "--.-"); res.put('r', ".-."); res.put('s', "..."); res.put('t', "-");
            res.put('u', "..-"); res.put('v', "...-"); res.put('w', ".--"); res.put('x', "-..-");
            res.put('y', "-.--"); res.put('z', "--..");
            Set<String> set = new HashSet<>();
            int count = 0;
            for(String word : words){
        
                String str = "";
                for(char ch : word.toCharArray()){
        
                    str = str + res.get(ch);
                }
                if(!set.contains(str)){
        
                    set.add(str);
                    count ++;
                }
            }
            
            return count;
        }
    }