-2

I'm trying to write a function in Python that will return True or False based on string matching, to see if a given list of word-parts, mixed and matched, can form a word.

The two inputs would be the word and the list of parts.

Some examples:

  • Inputs: word = 'hello', parts = ['hel', 'hol', 'llo', 'he'], Output: True

  • Inputs word = 'world', parts = ['woo', 'wor', 'rld', 'or'], Output: False

kaya3
  • 41,043
  • 4
  • 50
  • 79
casablanca62
  • 9
  • 4
  • 4
    Sounds good, what have you tried so far? – Selcuk Nov 29 '19 at 01:37
  • Possible duplicate of [Syllable Count In Python](https://stackoverflow.com/questions/46759492/syllable-count-in-python) – PL200 Nov 29 '19 at 01:54
  • 1
    That question is not a duplicate; in fact, this question doesn't really have anything to do with syllables or counting. – kaya3 Nov 29 '19 at 02:02
  • Possible duplicate of [Detecting syllables in a word](https://stackoverflow.com/questions/405161/detecting-syllables-in-a-word) – lbragile Nov 29 '19 at 03:32
  • I'm going to edit the question so people won't think it's a natural language processing problem. – kaya3 Nov 29 '19 at 03:45
  • You can find a solution here: https://stackoverflow.com/questions/5996621/algorithm-for-checking-if-a-string-was-built-from-a-list-of-substrings – aminrd Nov 29 '19 at 18:38

1 Answers1

0

This is a naturally recursive problem. Let's take ['hel', 'hol', 'llo', 'he'] as an example, where the goal is to make the word 'hello':

  • 'hel' is a possible start; it works if 'lo' can be formed from ['hol', 'llo', 'he']. This is a smaller instance of the same problem, and the answer is no, 'lo' can't be formed. So we continue.
  • 'hol' is not a possible start, so skip it.
  • 'llo' is also not a possible start.
  • 'he' the next option; it works if 'llo' can be formed from ['hel', 'hol', 'llo']. This is another smaller instance of the same problem, and the answer is yes, so we stop.

The algorithm is quite straightforward: for each part, if the word starts with that part, then try to recursively form the remainder of the word using the remainder of the list of parts.

The base case is the empty string: it can always be formed. Hopefully that gives you enough to go on.

kaya3
  • 41,043
  • 4
  • 50
  • 79