Splitting a hashtag into words

Hashtags join words without spaces, and tag does not include the # sign. Complete the function solution, which returns the number of ways to cut the hashtag tag into pieces so that every piece is a word in the word list words and no letters are left over from the start to the end.

The same word may be used more than once. Two ways are different if they cut at different positions. A word listed more than once in words still counts as one word. If the whole tag is one word, not cutting it is also one way. If tag cannot be cut this way, return 0.

Function

solution(tag, words)

Constraints

• tag is a string of lowercase English letters, with a length from 1 to 100.
• The length of words is from 1 to 50.
• Each word in words is a string of lowercase English letters, with a length from 1 to 10.
• The answer can be a very large number. Return it as a Python integer as it is, without taking a remainder.

Examples

Starter code

def solution(tag, words):
    answer = 0
    return answer