lc-139

/**
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.


 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



 Constraints:


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

 Related Topics字典树 | 记忆化搜索 | 哈希表 | 字符串 | 动态规划

 👍 1773, 👎 0

*/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>();

        Map<Integer, Boolean> resultMap = new HashMap<>();

        for (String word : wordDict) {
            wordSet.add(word);
        }

        return isValid(s, 0, wordSet, resultMap);
    }

    private boolean isValid(String s, int index, Set<String> wordSet, Map<Integer, Boolean> resultMap) {
        if (resultMap.containsKey(index)) {
            return resultMap.get(index);
        }

        if (index >= s.length()) {
            resultMap.put(index, true);
            return true;
        }

        if (wordSet.contains(s.substring(index, s.length()))) {
            resultMap.put(index, true);
            return true;
        }

        for (int i = s.length() - 1; i > index; i--) {
            String str = s.substring(index, i);

            if (wordSet.contains(str) && isValid(s, i, wordSet, resultMap)) {
                resultMap.put(index, true);
                return true;
            }
        }
        resultMap.put(index, false);
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)