March 17, 2017
[ I was visiting my daughter in Houston this week, and unbeknownst to me her computer was fried by lightning a few weeks ago; she was waiting for me to visit so I could advise her what to do. I’m typing this exercise on my tablet, where typing lots of words is difficult and typing code is nearly impossible. I’ll add code when I get back home in a few days. ]
There is an ambiguity in the problem definition, which is probably purposeful on the part of the interviewer. The word tact can be formed from the three letters a, c and t only if duplicates are permitted. In that case, the simple algorithm is to insert the characters in a set, then reject each word in the list that has a letter not in the set:
(define (alpha-set cs) (let ((s (make-vector 26 #f))) (do ((cs cs (cdr cs))) ((null? cs) s) (let ((t (- (char->integer (car cs)) 97))) (vector-set! s t #t))))
(define (word-set s word) (let loop ((cs (string->list word))) (if (null? cs) #t (let ((t (- (char->integer (car cs)) 97))) (if (vector-ref s t) (loop (cdr cs)) #f)))))
> (define s (alpha-set '(#\a #\c #\t))) > (word-set s "act") #t > (word-set s "tact") #t > (word-set s "stop") #f
Here, the set of input characters is stored in the
alpha vector; it could be stored in other ways — a hash table, a binary tree, something else — if desired. We are assuming all the letters are lower case.
If duplicates aren’t allowed, you have to count. Our solution keeps an array of length 26, and initializes each array slot with the number of available copies of the corresponding letter. Then each word is examined, and the count of each letter in the word is reduced each time it appears. If any count is ever negative, the word is rejected:
(define (alpha-count cs) (let ((c (make-vector 26 0))) (do ((cs cs (cdr cs))) ((null? cs) c) (let ((t (- (char->integer (car cs)) 97))) (vector-set! c t (+ (vector-ref c t) 1))))))
(define (word-count c word) (let ((c (vector-copy c))) (let loop ((cs (string->list word))) (if (null? cs) #t (let ((t (- (char->integer (car cs)) 97))) (vector-set! c t (- (vector-ref c t) 1)) (if (negative? (vector-ref c t)) #f (loop (cdr cs))))))))
> (define c (alpha-count '(#\a #\c #\t))) > (word-count c "act") #t > (word-count c "tact") #f > (word-count c "stop") #f
alpha vector stores letter counts instead of booleans. The letter counts are updated after each input character, so the vector must be copied afresh for each word that is tested.
You can run the program at http://ideone.com/mQoc3j.
Pages: 1 2