Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

&nbsp;
Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".


Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.


Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 300
	1 &lt;= wordDict.length &lt;= 1000
	1 &lt;= wordDict[i].length &lt;= 20
	s and wordDict[i] consist of only lowercase English letters.
	All the strings of wordDict are unique.


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        memo = {}


        def can_construct(target, strings_bank, memo):    
            if target in memo:
                return memo[target]
            if target == "":
                return True
            for element in strings_bank: # for every element in our dict we check if we can start constructing the string "s"
                if element == target[0:len(element)]: # the remaining of the string "s" (which is the suffix) is the new target 
                    suffix = target[len(element):]
                    if can_construct(suffix, strings_bank, memo):
                        memo[target] = True
                        return True
            memo[target] = False
            return False


        return can_construct(s, wordDict, memo)
class Solution {
     Map<String,Boolean>map= new HashMap<>();
    public boolean wordBreak(String s, List<String> wordDict) {

       if(wordDict.contains(s)){
           return true;
       }
        if(map.containsKey(s)){
           return map.get(s);
        }
        for(int i=0;i<s.length();++i){
            String left=s.substring(0,i);
            if(wordDict.contains(left) && wordBreak(s.substring(i),wordDict)){
                map.put(s,true);
                return true;
            }
        }
        map.put(s,false);
        return false;
    }
}
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int m = wordDict.size();
        int n = s.size();
        vector<int> dp(n+1,0);
        dp[0] = 1;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(i >= wordDict[j].size())
                {
                    for(int k = 0; k < wordDict[j].size(); k++)
                    {
                        if(s[i-wordDict[j].size()+k] != wordDict[j][k])
                            goto cnt;
                    }
                    if(dp[i-wordDict[j].size()] == 1) 
                        dp[i] = 1;
                    if(dp[n] == 1) 
                        return true;
                    cnt:;
                }
            }
        }
        return dp[n];
    }
};
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    var dp = new Array(s.length + 1).fill(false);
    dp[s.length] = true;

    for (var i = s.length - 1; i >= 0; i--) {
        for (const word of wordDict) {
            if ((i + word.length) <= s.length
                && s.substring(i, i + word.length) === word) {
                dp[i] = dp[i + word.length];
            }

            if(dp[i]) break;
        }
    }

    return dp[0];
};

// naive approach, take each word from the set and check if they match
/// O(n ^ 2 * m)
// considering m as the dictionary size
/*
var dict = new Set();
for (const word of wordDict) {
    dict.add(word);
}

return canSegment(s, dict, 0);

function canSegment (str, dict, index) {
    if (index >= str.length) return true;

    var success = false;
    for (const word of dict.values()) {

        if ((index + word.length) <= str.length) {
            var substring = str.substring(index, index + word.length);

            if (dict.has(substring)) {
                success = success | canSegment(str, dict, index + word.length);
            }
        }
    }

    return success;
}
*/
Word Break