5
\$\begingroup\$

I've come across a simple challenge: given a phrase, check if we can form the given word vertically by stacking words in rows. For example, we can form the word "boom" from this phrase:

   every breath
            you take
every move
      you make

My Python code:

def can_spell(s, w):
    words = s.split()
    words_iter = iter(words)

    for char in w:
        try:
            next_word = next(words_iter)
            while char not in next_word:
                next_word = next(words_iter)
        except StopIteration:
            return False
    return True


print(can_spell('every breath you take every move you make', 'boom'))  # True

Is this the most efficient way to do it?

\$\endgroup\$
4
\$\begingroup\$

Staying close to your original appraoch, you could use another for loop with an else instead of try/except and while. The else is triggered when the inner loop has ended normally, without the break, i.e. when there are no more parts left in the sentence.

def can_spell(sentence, word):
    words_iter = iter(sentence.split())
    for char in word:
        for part in words_iter:
            if char in part:
                break
        else:
            return False
    return True

Or, you could use a nested generator expression checking that all characters in the word are in any of the remaining parts of the sentence-iterator. This works since any will only consume as many items from the iterator as necessary until it finds a match.

def can_spell(sentence, word):
    words_iter = iter(sentence.split())
    return all(any(char in part for part in words_iter) for char in word)

Following an entirely different route, you could use a regular expression, joining the characters of the word such that between each character there has to be at least one space (and, optionally, any other characters), e.g. b.* .*o.* .*o.* .*m for boom, and check if that regular expression can be found in the sentence:

import re
def can_spell(sentence, word):
    return re.search('.* .*'.join(word), sentence) is not None
\$\endgroup\$
  • \$\begingroup\$ For each appraoch, performance should be O(n) with n being the number of characters in the sentence. timeit was inconclusive due to caching. \$\endgroup\$ – tobias_k Oct 19 '18 at 9:49
  • \$\begingroup\$ Nice regex approach. I would use .*\s+.* (properly escaped of course) to catch tabs or newlines between words. I’d be tempted to explore .*\b.* too; depends on how you define a word. \$\endgroup\$ – AJNeufeld Oct 19 '18 at 14:27
  • \$\begingroup\$ @AJNeufeld Agreed, but from the question I'd guess that the "sentence" will always be just a space-separated list of lower-case words, not line breaks, tabs or punctuation. \$\endgroup\$ – tobias_k Oct 19 '18 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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