139 Word Break

Given anon-emptystring_s_and a dictionary_wordDict_containing a list ofnon-emptywords, determine if_s_can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

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

Solution)

class Solution {
    Set<String> map = new HashSet();
    public boolean wordBreak(String s, List<String> wordDict) {
        if(wordDict.contains(s)) return true;
        if(map.contains(s)) return false;
        for(String word : wordDict){
            if(s.startsWith(word)){
                if(wordBreak(s.substring(word.length()), wordDict)) return true;
            }
        }
        map.add(s);
        return false;
    }  
}