Google – Shortest Words Contain Input String

Google – Shortest Words Contain Input String
Related: Google – Plate and Dictionary
Input一个字典，和一个string, 要求返回dict里包含所有string里所有character且长度最短的word。
比如input "df", dict = [cat, act, tac, dsf, asdf]
返回dsf

[Solution]
建Inverted Index
还有一种方法类似Google – Plate and Dictionary 的第三种解，把26个字母都map成prime number然后做乘积。
下面代码是Inverted Index的方法。

  Map<Character, List<String>> invertedIndex = new HashMap<>();

  public Solution(String[] dict) {

    if (dict == null || dict.length == 0) {

      return;

    }

     

    for (String s : dict) {

      for (char c : s.toCharArray()) {

        invertedIndex.putIfAbsent(c, new ArrayList<>());

        invertedIndex.get(c).add(s);

      }

    }

  }

   

  public String query(String input) {

    if (input == null || input.isEmpty()) {

      return null;

    }

    Set<String> set = new HashSet<>();

    for (char c : input.toCharArray()) {

      if (set.isEmpty()) {

        set.addAll(invertedIndex.get(c));

      }

      else {

        set.retainAll(invertedIndex.get(c));

      }

    }

     

    String result = null;

    for (String s : set) {

      if (result == null || s.length() < result.length()) {

        result = s;

      }

    }

    return result;

  }

Read full article from Google – Shortest Words Contain Input String