Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
given a string, determine whether it is a concatenation of english words
; given a string, determine whether it is a concatenation of english words
; string of digits only is considered an english word
; assume that strings are lower cased
; empty string: don't care
(defn word? [w]
(or (re-matches #"[0-9]" w)
(contains? #{"go" "hi" "my" "cat" "is" "nice" "mymy" "mymymy"} w)))
(declare concatenated_words-inner?)
(defn word-and-words? [stored-results s i]
(and
(word? (subs s 0 i))
(concatenated_words-inner? stored-results (subs s i))))
(defn concatenated_words-inner? [stored-results s]
(let [stored-res (get @stored-results (count s))]
(if (nil? stored-res)
(let [res (if (empty? s)
true
(not-every? false? (map (partial word-and-words? stored-results s) (range 1 (inc (count s))))))]
(swap! stored-results assoc (count s) res)
res)
stored-res)))
(defn concatenated_words? [s]
(concatenated_words-inner? (atom (vec (repeat (count s) nil))) s))
; tests
(= false (concatenated_words? "c"))
(= true (concatenated_words? "1"))
(= true (concatenated_words? "12"))
(= true (concatenated_words? "cat"))
(= true (concatenated_words? "mycat"))
(= false (concatenated_words? "mybkcat"))
(= false (concatenated_words? "mybcat"))
(= true (concatenated_words? "mycatiscat"))
(= true (concatenated_words? "mymymymymymymymymy"))
(= false (concatenated_words? "mymymymymymymymymyk"))
(= true (concatenated_words? "my2cat89"))
(= true (concatenated_words? "my2cat89isnice"))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.