Below are two implementations of the problem "find the characters in common between two strings" - in Clojure without using collections / set operations.
Are these approaches sufficiently idiomatic and could the be more concise? (aside from using collections functions).
Also, is there a Clojure library that wraps or provides an alternative to
;; Approach #1 BitSets ;; - use a bitsets for each string, ;; - flip the bit for each character in each string ;; - then "and" the two bitsets. Theoretically O(N + M) performance (defn string-to-charbits [s] (loop [[f & rest] s bits (java.util.BitSet.)] (if f (recur rest (do (.set bits (int f)) bits)) bits))) (defn process-bitset [bitset] (loop [bitset bitset count 0 result '] (if (< count (.length bitset)) (recur bitset (inc count) (if (.get bitset count) (conj result (char count)) result)) result))) (defn find-matching-chars [s1 s2] (let [b1 (string-to-charbits s1) b2 (string-to-charbits s2)] (do (.and b1 b2) (process-bitset b1)))) ;; Approach #2 - Brute Force ;; For each character in string 1, linear search (via .indexOf) of string 2 ;; Theoretically O(N * M) performance (defn find-matching-chars-brute [s1 s2] (loop [[f & rest] s1 s2 s2 result ] (if f (if (> (.indexOf s2 (int f)) -1) (recur rest s2 (conj result f)) (recur rest s2 result)) (distinct result)))) ;; Might need to sort the results of each function call to make this pass (assert (= (find-matching-chars "abcd" "cde") (find-matching-chars-brute "abcd" "cde")) "expected [\\c \\d]")