group_anagrams.ml

(* ctci 11.2: Write a method to sort an array of strings so that all the
 * anagrams are next to each other. *)

let group_anagrams (xs : string array) : unit =
  let join (xs : char array) : string =
    String.concat_array (Array.map ~f:Char.to_string xs) in
  let key (s : string) : string =
    let chars = String.to_array s in
    Array.sort chars ~cmp:Char.compare;
    join chars in
  let table = String.Table.create () in
  Array.iter xs ~f:(fun s -> Hashtbl.add_multi table ~key:(key s) ~data:s);
  let i = ref 0 in
  Hashtbl.iter_vals table ~f:(fun ys ->
      List.iter ys ~f:(fun s -> xs.(!i) <- s; incr i));