Daily Archives: January 10, 2015

Jaccard distance

This is to response Junmin Liu’s Jaccard distance problem.
For example:
two strings: adbc and adffg, result is 2 / 6
(size of intersect of chars in strings) / (size of union of chars in strings). and duplicate character can only count once.

I came up with 2 solutions:
1. O(m+n) time, O(m+n) space with hashset
2. O((m+n)log(m+n)) time, O(1) space by sorting.
Below is my code:

  1. import java.util.Arrays;
  2. import java.util.HashSet;
  3. public class Jaccard {
  4.     public static void main(String[] args) {
  5.         char[] str = {‘a’, ‘f’, ‘g’, ‘e’, ‘a’, ‘c’, ‘a’, ‘d’, ‘f’, ‘b’, ‘q’};
  6.         int pos = 5;
  7.         calJacDistance(str, pos);
  9.         char[] a = {‘a’, ‘b’, ‘c’, ‘d’,’e’,’g’};
  10.         char[] b = {‘a’, ‘d’, ‘f’, ‘f’, ‘g’};
  11.         calJacDistance2(a, b);
  12.     }
  14.     /*
  15.      * Time O(m+n), space O(m+n)
  16.      */
  17.     public static void calJacDistance2(char[] a, char[] b){
  18.         if(a==null||b==null||a.length<1||b.length<1){
  19.             return;    //lenght of b[] is zero.
  20.         }
  21.         HashSet hs1 = new HashSet();
  22.         HashSet hs2 = new HashSet();
  23.         for(int i=0;i
  24.             hs1.add(a[i]);
  25.         }
  26.         for(int i=0;i
  27.             hs2.add(b[i]);
  28.         }
  29.         //put elements from hs2 to hs1. During this process, record how many duplication it is.
  30.         int dup_num = 0;
  31.         for(char ch:hs2){
  32.             if(hs1.contains(ch)){
  33.                 dup_num++;
  34.             }
  35.             else{
  36.                 hs1.add(ch);
  37.             }
  38.         }
  39.         int union_num = hs1.size();
  40.         System.out.println((double)dup_num / (double)union_num);
  41.     }
  43.     /*
  44.      * The idea of this solution is to sort and find the duplicaitons.
  45.      * str[0,…,pos] is the a[], str[pos+1,…,len-1] is b[]
  46.      * time O[(m+n)log(m+n)], space O(1).
  47.      * time mostly is costed by sorting.
  48.      */
  49.     public static void calJacDistance(char[] str, int pos){
  50.         if(pos==str.length-1||pos<0){
  51.             return;    //lenght of b[] is zero.
  52.         }
  53.         Arrays.sort(str, 0, pos+1);
  54.         Arrays.sort(str, pos+1, str.length);
  55.         //below 2 for loop is to deduplicate a[] and b[] separately
  56.         int dup_num = 0;    //to record how many duplication are there in str.
  57.         for(int i=1;i<=pos;i++){
  58.             if(str[i]==str[i-1-dup_num]){
  59.                 dup_num++;
  60.             }
  61.             else{
  62.                 str[i-dup_num] = str[i];
  63.             }
  64.         }
  65.         str[pos+1-dup_num] = str[pos+1];
  66.         for(int i=pos+2;i
  67.             if(str[i]==str[i-1-dup_num]){
  68.                 dup_num++;
  69.             }
  70.             else{
  71.                 str[i-dup_num] = str[i];
  72.             }
  73.         }
  74.         Arrays.sort(str, 0, str.length -dup_num);    //sort the new array
  75.         //duplication number in str[0,…,len-dup_num-1] will be the intersection number
  76.         //str.len-dup_num-dup_num2 will be the union number
  77.         int dup_num2 = 0;
  78.         for(int i=1;i
  79.             if(str[i]==str[i-1-dup_num2]){
  80.                 dup_num2++;
  81.             }
  82.             else{
  83.                 str[i-dup_num2] = str[i];
  84.             }
  85.         }
  86.         int union_num = str.length – dup_num – dup_num2;
  87.         System.out.println((double)dup_num2 / (double)union_num);
  88.     }
  89. }