Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.

For example, consider the following dictionary: { pear, salmon, foot, prints, footprints, leave, you, sun, girl, enjoy },

Examples:

Given the string youenjoy,

Output: True (The string can be segmented as you enjoy)

Input: youleavefootprints,

Output: True (The string can be segmented as you leave footprints or you leave foot prints)

Input:salmonenjoyapples

Output: False

c++

comment code

optimize code for best running time

write algorithm you used with words