Zenn
📑

LeetCode 2020-11-22: Unique Morse Code Words

2020/11/25に公開
Java
LeetCode
tech

Unique Morse Code Words (easy) の挑戦メモです。

問題の概要

  • 配列で与えられる複数の文字列について、それぞれをモールス符号で表現したときの文字列の異なり数を求める

考え方

  • 実際に文字列をモールス符号の列に置き換えて HashSet などに突っ込めば簡単に解ける問題ですね
    • ただ問題をよくよく見てみると、文字列の長さは最大で 12 文字、対してモールス符号は最長でも 4 ビットになるので、これはモールス符号に置き換えた文字列を long で表現せよ、ということの暗示ぽいですね
  • モールス符号の列に置き換えた文字列を long で表すとして、あとはこれからどうやって異なり数を求めるかを考えてみよう 🤔
    • これを HashSet に入れるのは芸がないよね…
    • long の値を保持するハッシュテーブルを自前実装してしまえばいいのでは？
    • 文字列の数は最大でも 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