Programming Praxis

We work with two words at a time, repeating as needed for longer lists. Our method sorts the letters of the two words in order, then scans the two lists, keeping characters that match:

(define (common x-str y-str)
  (let loop ((xs (sort charlist x-str)))
             (ys (sort charlist y-str)))
             (zs (list)))
    (cond ((or (null? xs) (null? ys))
            (list->string (reverse zs)))
          ((char<? (car xs) (car ys))
            (loop (cdr xs) ys zs))
          ((char<? (car ys) (car xs))
            (loop xs (cdr ys) zs))
          (else (loop (cdr xs) (cdr ys)
                      (cons (car xs) zs))))))

(define (common-chars . words)
  (fold-left common (car words) (cdr words)))

And here’s the sample problem:

> (common-chars "bella" "label" "roller")
"ell"

You can run the program at https://ideone.com/MVtnY0.

The sample solution at the coding challenge site looks like this:

public List commonChars(String[] A) {
        List ans = new ArrayList();
        int[] count = new int[26]; 
        Arrays.fill(count, Integer.MAX_VALUE);
        for (String str : A) {
            int[] cnt = new int[26];
            for (char c : str.toCharArray()) { ++cnt[c - 'a']; } // count each char's frequency in string str.
            for (int i = 0; i < 26; ++i) { count[i] = Math.min(cnt[i], count[i]); } // update minimum frequency.
        }
        for (char c = 'a'; c  0) { ans.add("" + c); }
        }
        return ans;
    }

That solution has four for loops and one while loop (some of them nested), an ArrayList data structure for the return value, an int[] array for each word plus another int[] array for the totals (and their names cnt and count are sure to be confused), lots of funny character arithmetic, and the magic numbers 26 and 'a' and 'z' and Integer.MAX_VALUE. With all that complexity it takes a few minutes of slow reading for the underlying algorithm to become apparent. I like my solution better.

Pages: 1 2