17 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:
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, “cba” can be written as “-.-…–…”, (which is the concatenation “-.-.” + “-…” + “.-”). We’ll call such a concatenation, the transformation of a word.
Return the number of different transformations among all words we have.
Example: 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 “–…--.”.
Note:
The length of words will be at most 100.
Each words[i] will have length in range [1, 12].
words[i] will only consist of lowercase letters.分析
题意：给定一个字符串数组，将其转换成摩斯密码，然后返回这些摩斯密码的组数（相同的摩斯密码为一组）
思路： 首先肯定是将每个字符串转换成摩斯密码，只需要遍历每个字符串，按转换规则转换即可； 然后计算不同摩斯密码的组数： 有两种方法：
- 初始化一个计数器，遍历所有摩斯密码对比即可，不同时将计数器+1。
- 将所有摩斯密码进行去重，然后计算去重后的个数（set有自动去重功能）
解答
下面答案摘自评论区大神解答，非常的巧妙。解释在注释中
class Solution {
public int uniqueMorseRepresentations(String[] words) {
String[] d = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."};
//创建一个Set，用于存放最终结果，实现自动去重
Set<String> s = new HashSet<>();
//遍历每个字符串，假设现在是words={"gin","zen"}
for (String w : words) {
//此时w="gin"
//创建一个临时的字符串，用于存放转码后的摩斯密码，用StringBuilder是因为它有append函数
StringBuilder sb = new StringBuilder();
for (int i = 0; i < w.length(); ++i)
//i=0, w.charAt(i)='g'
/*
这就是最巧妙的地方
摩斯密码转换表对应的是26个大小写字母，char底层实现是int，
利用w.charAt(i)='g'-'a'，能够得到'g'在摩斯密码数组中的下标，
通过d[w.charAt(i) - 'a']，就能拿到'g'对应的摩斯码
*/
//将摩斯码加入到临时字符串中
sb.append(d[w.charAt(i) - 'a']);
//将临时字符串加入到set集合
s.add(sb.toString());
}
//最终返回集合的长度即可，重复的摩斯码已经被忽略了。
return s.size();
}
}上述算法的亮点就在于，通过d[w.charAt(i) - ‘a’]，实现了字母到摩斯码的映射。
腾讯云开发者
