Write a function

Community Jobs
1

I need to write a function that takes two lists (list1, list2) and returns true if the lists are anagrams.
Two lists are anagrams if the elements from one may be rearranged to get the
other.

2

An easy-to-write solution (O(n log n)) would be to sort both lists and check whether the results are equal.

let anagram l1 l2 =
  List.sort compare l1 = List.sort compare l2

Another way (maybe faster, I still have not computed the complexity) would be to go through l1 and making an associative list or a map counting the items, and going through l2 and doing the same, and checking the results. Or making a multi-set with all the elements from the first list, and removing them one by one when reading them in the second list… There are plenty of possibilities.

1 Like
3

Assuming you have 'a list, you could

  • create a hashtbl of type 'a list to int
  • for each item in the first array, increment the value at key item in the hashtbl (assuming a default value of 0)
  • for each item in the second array, if present in the hashtbl and greater than 0, decrement the value at key item, otherwise the lists are not anagrams
  • enumerate through the values held in the hashtbl and the lists are anagrams if none of them are different from 0.

Compared to @cloudyhug’s solution, this one theoretically has a better worst-case time complexity O(n+m) but has a O(n) space complexity since all entries from the first array might be different and that we need to count for each distinct entry.

Also note that even though the space complexity of @cloudyhug’s algorithm with an inplace sort looks like it’s O(1), the sorting algorithm might itself use some stack space (ex.: log(n) for quicksort).

I hope this was somewhat helpful?

1 Like
4

That’s what I was talking about, an element-counting-based solution is nicer indeed. Something with sets allows not having to increment or decrement a value at all. You just add the elements one by one, and check the set equality :

open Core

let anagram l1 l2 =
  Set.equal
    (List.fold_left ~init:Set.empty ~f:Set.add l1)
    (List.fold_left ~init:Set.empty ~f:Set.add l2)

I have never used Core, so I’m not sure if the syntax is correct. I know the data structure implementations are really efficient though, so the time complexity is linear.

PS : Welcome to OCaml Discuss !