📑
LeetCode 2020-11-22: Unique Morse Code Words
Unique Morse Code Words (easy) の挑戦メモです。
問題の概要
- 配列で与えられる複数の文字列について、それぞれをモールス符号で表現したときの文字列の異なり数を求める
考え方
- 実際に文字列をモールス符号の列に置き換えて
HashSet
などに突っ込めば簡単に解ける問題ですね- ただ問題をよくよく見てみると、文字列の長さは最大で 12 文字、対してモールス符号は最長でも 4 ビットになるので、これはモールス符号に置き換えた文字列を long で表現せよ、ということの暗示ぽいですね
- モールス符号の列に置き換えた文字列を long で表すとして、あとはこれからどうやって異なり数を求めるかを考えてみよう 🤔
- これを
HashSet
に入れるのは芸がないよね… - long の値を保持するハッシュテーブルを自前実装してしまえばいいのでは?
- 開番地法 (open addressing) で実装すればそんなに難しくないよね
- 文字列の数は最大でも 100 なので、ハッシュテーブルの大きさは 256 ぐらいで十分でしょ
- ハッシュ値計算は実際に 256 未満になるように調整するとして、linear probing で 256 以上の値になったときのことを考えてわざと大きめにハッシュテーブルを確保しておこう
- これを
- 実装して submit → Runtime 1ms
Your runtime beats 99.96 % of java submissions.
👍 - Runtime 0ms 達成しようとして試行錯誤してみたが、ちょっと無理だった 😭
- 実際に 0ms 達成しているコードを見てみたけど、long 値のハッシュテーブルを利用するアプローチは同じだった
コード
class Solution {
static final byte[] CODES = {0b01, 0b1000, 0b1010, 0b100, 0b0, 0b0010, 0b110, 0b0000, 0b00, 0b0111, 0b101, 0b0100, 0b11, 0b10, 0b111, 0b0110, 0b1101, 0b010, 0b000, 0b1, 0b001, 0b0001, 0b011, 0b1001, 0b1011, 0b1100};
static final byte[] CODE_LENGTHS = {2, 4, 4, 3, 1, 4, 3, 4, 2, 4, 3, 4, 2, 2, 3, 4, 4, 3, 3, 1, 3, 4, 3, 4, 4, 4};
public int uniqueMorseRepresentations(String[] words) {
long[] hashTable = new long[512];
int count = 0;
for (String word : words) {
long wordCodes = 0;
for (int i = 0; i < word.length(); i++) {
int ch = word.charAt(i) - 'a';
wordCodes = (wordCodes << CODE_LENGTHS[ch]) | CODES[ch];
}
wordCodes++;
int hashVal = (int) (((wordCodes >> 40)
^ ((wordCodes >> 32) & 0xff)
^ ((wordCodes >> 24) & 0xff)
^ ((wordCodes >> 16) & 0xff)
^ ((wordCodes >> 8) & 0xff)
^ (wordCodes & 0xff)) & 0xffL);
for (int i = hashVal; hashTable[i] != wordCodes; i++) {
if (hashTable[i] == 0) {
hashTable[i] = wordCodes;
count++;
break;
}
}
}
return count;
}
}
Discussion