leetcode Daily Challenge on November 22th, 2020
Difficulty : Easy
Related Topics : String
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, "cab" 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.
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 "--...--.".
- The length of
words
will be at most100
.- Each
words[i]
will have length in range[1, 12]
.words[i]
will only consist of lowercase letters.
- mine
- Java
Runtime: 1 ms, faster than 99.96%, Memory Usage: 36.9 MB, less than 67.82% of Java online submissions
// O(N)time // O(N)space // N is the all char count public int uniqueMorseRepresentations(String[] words) { if(words == null || words.length == 0) return 0; String[] encode = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."}; Map<String,Integer> resMap = new HashMap<>(); for(int i = 0; i < words.length; i++){ String temp = words[i]; char[] s = temp.toCharArray(); StringBuilder sb = new StringBuilder(); for(int j = 0; j < s.length; j++){ sb.append(encode[s[j] - 'a']); } resMap.put(sb.toString(),1); } return resMap.size(); }
- Java
- the most votes
Runtime: 1 ms, faster than 99.96%, Memory Usage: 36.8 MB, less than 67.82% of Java online submissions
// O(S)time // O(S)space // S is the sum of the lengths of words in words public int uniqueMorseRepresentations(String[] words) { String[] MORSE = new String[]{".-","-...","-.-.","-..",".","..-.","--.", "....","..",".---","-.-",".-..","--","-.", "---",".--.","--.-",".-.","...","-","..-", "...-",".--","-..-","-.--","--.."}; Set<String> seen = new HashSet(); for (String word: words) { StringBuilder code = new StringBuilder(); for (char c: word.toCharArray()) code.append(MORSE[c - 'a']); seen.add(code.toString()); } return seen.size(); }