# Check if we can form a word across words in a sentence

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?

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

• For each appraoch, performance should be O(n) with n being the number of characters in the sentence. timeit was inconclusive due to caching. – tobias_k Oct 19 '18 at 9:49
• 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. – AJNeufeld Oct 19 '18 at 14:27
• @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. – tobias_k Oct 19 '18 at 15:04