leetCode：「Add and Search Word - Data structure design」

leetCodeの「Add and Search Word - Data structure design」を解いてみた。
https://leetcode.com/problems/add-and-search-word-data-structure-design/

この問題は、簡易版の辞書を作成するというもの。機能としては、単語の登録と検索がある。検索では「.」を任意の一文字として指定することができる。

実装する上で気にしたのは以下の点。

• 単語の検索の速度を上げるため、「登録単語の長さ→その長さの単語群」のハッシュマップに単語を登録して、検索時はまず検索単語の長さでフィルタリングする。
• 「.」を扱うのに正規表現用のJava標準API使用すると速度が遅かったので、その部分は独自で実装した。

提出したコードは以下。

import java.util.*;
// import java.util.concurrent.ConcurrentHashMap;

class WordDictionary {

    Map<Integer, List<String>> lengthToWords = new HashMap();
    // WordDictionaryがマルチスレッドからアクセスされるなら以下にする。
    // Map<Integer, List<String>> lengthToWords = new ConcurrentHashMap();

    /** Initialize your data structure here. */
    public WordDictionary() {

    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        int length = word.length();
        if (lengthToWords.containsKey(length)) {
            lengthToWords.get(length).add(word);
        }
        else {
            List<String> words = new ArrayList();
            words.add(word);
            lengthToWords.put(length, words);
        }
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String regex) {
        List<String> candidates = lengthToWords.get(regex.length());
        if (candidates == null) {
            return false;
        }
        for (String candidate : candidates) {
            // 以下のように正規表現用のAPI (String#matches) を使うと、速度がだいぶ遅くなる。
            // if (candidate.matches(regex)) {

            if (isMatched(candidate, regex)) {
                return true;
            }
        }
        return false;
    }

    private boolean isMatched(String word, String regex) {
        for (int i = 0; i < word.length(); i++) {
            if ((word.charAt(i) != regex.charAt(i)) && (regex.charAt(i) != '.')) {
                return false;
            }
        }
        return true;
    }
}

これを提出すると、以下のように、ほとんどの提出者よりも速い結果となった。メモリ量も少なく済んでいる。

Runtime: 29 ms, faster than 99.95% of Java online submissions for Add and Search Word - Data structure design.
Memory Usage: 50.9 MB, less than 100.00% of Java online submissions for Add and Search Word - Data structure design.

他の人の解き方を見たところ、trie木を使って解いているものが多かったので、後日、この方法でも解いてみる。