Find the common characters between two strings without using set operations

Question

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 java.util.BitSet?

;; 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]")

Answer 1

With your restrictions, yes, that seems fairly idiomatic. I am not aware of a good bitset implementation yet -- wrapping java.util.BitSet wouldn't work that well, since a clojure version would want to be persistent. That said, your restrictions are not idiomatic at all. Presumably, you don't want to use clojure.set/intersection (and completely trivializing the problem), but something like

(defn find-matching-chars [s1 s2]
  (distinct (filter (into #{} s1) s2)))

really would be far more idiomatic. I could see using something like your BitSet code if find-matching-chars was actually causing significant performance issues, but short of that, some form of collections manipulation really is the idiomatic way to solve this issue.

In all honesty, my probable course in a situation like this would be to build filter and linked lists from scratch if I couldn't use the built-in versions, but at this point, I am probably straying away from idiomatic code myself.

Answer 2

I would create two arrays size ALPHABET (one for each string) and just set the corresponding array element to 1 if a char exists in string (like char_array[c - 'A'] = 1). Then scan two arrays parallel and check if the same element is set for both strings.

Pseudocode in python:

def find_matching_chars(s1, s2):
    ALPHABET = 'abcdefghijklmnopqrstuvwxyz'
    ALPHABET_LEN = len(ALPHABET)
    char_array1  = [0]*ALPHABET_LEN
    char_array2  = [0]*ALPHABET_LEN
    for c in s1:
        char_array1[ord(c)-ord('a')] = 1
    for c in s2:
        char_array2[ord(c)-ord('a')] = 1
    result = [] 
    for index in xrange(len(char_array1)):
        if char_array1[index] != 0 and char_array2[index] != 0:
          result.append(ALPHABET[index])  
    return result

print find_matching_chars("abcd", "cde")

Answer 3

I prefer doseq to loop when iterating over either a collection or a sequence.

(defn string-to-charbits [s]      
  (let [bits (java.util.BitSet.)] 
    (doseq [c s]                  
      (.set bits (int c)))        
    bits))