Given a dictionary containing many words, find the largest product of two words’ lengths, such that the two words do not share any common characters.

Assumptions

• The words only contains characters of 'a' to 'z'
• The dictionary is not null and does not contains null string, and has at least two strings
• If there is no such pair of words, just return 0

Examples

• dictionary = [“abcde”, “abcd”, “ade”, “xy”], the largest product is 5 * 2 = 10 (by choosing “abcde” and “xy”)

Solution: best first search. 先把dict按长度大到小排序，再把(0, 1, product)加入pq，每次弹出，检查是否有共同字母，再把(i + 1, j, product)和(i, j + 1, product)加入pq。用visited[][]去重（其实不去重也可以，不过效率降低）。

  public int largestProduct(String[] dict) {
    Arrays.sort(dict, new MyComparator());
    boolean[][] visited = new boolean[dict.length][dict.length];
    PriorityQueue<Node> pq = new PriorityQueue<>(1, new MyComparator2());
    pq.offer(new Node(0, 1, dict[0].length() * dict[1].length()));
    visited[0][1] = true;
    while (pq.size() > 0) {
      Node cur = pq.poll();
      if(noDuplicate(dict[cur.index1], dict[cur.index2])) {
        return cur.product;
      }
      if (cur.index1 + 1 < dict.length && cur.index1 + 1 != cur.index2 && !visited[cur.index1 + 1][cur.index2]) {
        pq.offer(new Node(cur.index1 + 1, cur.index2, dict[cur.index1 + 1].length() * dict[cur.index2].length()));
        visited[cur.index1 + 1][cur.index2] = true;
      }
      if (cur.index2 + 1 < dict.length && cur.index2 + 1 != cur.index1 && !visited[cur.index1][cur.index2 + 1]) {
        pq.offer(new Node(cur.index1, cur.index2 + 1, dict[cur.index1].length() * dict[cur.index2 + 1].length()));
        visited[cur.index1][cur.index2 + 1] = true;
      }
    }
    return 0;
  }
  private boolean noDuplicate(String a, String b) {
    Set<Character> hashset = new HashSet<>();
    for (int i = 0; i < a.length(); i++) {
      hashset.add(a.charAt(i));
    }
    for (int i = 0; i < b.length(); i++) {
      if (hashset.contains(b.charAt(i))) {
        return false;
      }
    }
    return true;
  }
  class Node {
    int index1, index2, product;
    public Node(int i1, int i2, int p) {
      index1 = i1;
      index2 = i2;
      product = p;
    }
  }
  class MyComparator implements Comparator<String> {
    public int compare(String a, String b) {
        return b.length() - a.length();
    }
  }
  class MyComparator2 implements Comparator<Node> {
    public int compare(Node a, Node b) {
        return b.product - a.product;
    }
  }

Solution 2: 利用26 bits记录每个单词的字母种类，1表示出现过，用|操作统计，得到一个数字，并计入hashmap (key: string, val: int)。判断2个单词是否有重复字母时，用val1 & val2 == 0