Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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]")
share|improve this question
add comment

3 Answers

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.

share|improve this answer
add comment

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")
share|improve this answer
    
Sorry, but downvote. I'm not looking for new techniques to solve the problem, I'm looking for feedback on my Clojure style / idiomatic usage. –  noahz Jul 11 '12 at 12:35
    
It's not a 'new techniques', it's just a simple BitSet alternative :) You don't need to use BitSet for limited alphabet - it's overhead. –  cat_baxter Jul 11 '12 at 13:24
    
Why are you assuming the alphabet is limited to a-z lower case. When I thought of this problem, I originally attempted to allocate an array of Character.MAX_VALUE –  noahz Jul 11 '12 at 13:35
    
It was just an example - you can use alphabet any size:) –  cat_baxter Jul 11 '12 at 13:45
add comment

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))
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.