Common Characters

May 14, 2019

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.

Advertisements

Pages: 1 2

3 Responses to “Common Characters”

  1. Globules said

    A Haskell version.

    import Data.List (foldr1, intersect)
    
    common :: Eq a => [[a]] -> [a]
    common []  = []
    common xss = foldr1 intersect xss
    
    main :: IO ()
    main = do
      print $ common ([] :: [String])
      print $ common ["BELLA"]
      print $ common ["BELLA", "LABEL"]
      print $ common ["BELLA", "LABEL", "ROLLER"]
    
    $ ./commchar
    ""
    "BELLA"
    "BELLA"
    "ELL"
    
  2. Paul said

    In Python.

    from collections import Counter
    from functools import reduce
    from operator import and_
    
    def common(listofwords):
        return list(reduce(and_, (Counter(w) for w in listofwords)).elements())
    
    print(common(["BELLA", "LABEL"]))  # -> ['B', 'E', 'L', 'L', 'A']
    print(common(["BELLA", "LABEL", "ROLLER"]))  # -> ['E', 'L', 'L']
    
  3. Daniel said

    Here’s a solution in C.

    #include <stdio.h>
    #include <stdlib.h>
    
    // Returns the result in s1
    void common(char* s1, char* s2) {
      int a1[26] = {0};
      int a2[26] = {0};
      char* _s1 = s1;
      for (; *s1; ++s1) {
        ++(a1[*s1 - 'a']);
      }
      for (; *s2; ++s2) {
        ++(a2[*s2 - 'a']);
      }
      int pos = 0;
      for (int i = 0; i < 26; ++i) {
        int count = a1[i] < a2[i] ? a1[i] : a2[i];
        for (int j = 0; j < count; ++j) {
          _s1[pos++] = 'a' + i;
        }
      }
      _s1[pos] = '\0';
    }
    
    int main(int argc, char* argv[]) {
      if (argc == 1) return EXIT_FAILURE;
      for (int i = 1; i < argc; ++i) {
        common(argv[1], argv[i]);
      }
      printf("%s\n", argv[1]);
      return EXIT_SUCCESS;
    }
    

    Example Usage:

    $ ./a.out bella label roller
    ell
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: