Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, 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

Explanation 1

We can use recursion to solve this problem.
Before we start, we put all the strings from the array into a set so that we can have constant time of accessing the element.
Create a one dimensional array memo[str.length] and initially set all elements are -1. memo[i] represents starting from index i of the string to the end, if memo[i]=0 then it means the string[i:end] cannot be form from the set; if dp[i]=1 then it means string[i:end] can be formed from the set.
For example, if string is abcd, then start is from index 0. We first check if a can be formed from the set, then we set the new start from b, and recursivly check if b can be found from the set, if yes, then we recursivly start from c (we will use memo array later); else if a cannot be found from the set, then we check if ab can be found from the set; if ab can be found from the set, then we set the new start from c (here start from c again, we will use a memo array to record if start from c the string can be found or not); if ab cannot be found from the set, then we check abc. Repeat the previous step, until start start hits str.length(). So, the recursive function will be memo[s]=set.contains(str[s:i)) && check(start=i). In other words, if string[s:i) is true and string[i:] can also be found from the set, then the string starts from index 0 can be formed by the set.

Solution 1

class Solution {
    boolean helper(String s, Set<String> set, int[] memo, int start) {
        if (start >= s.length()) return true;

        if (memo[start] != -1) {
            return memo[start] == 1;
        }

        for (int i = start+1; i <= s.length(); i++) {
            if (set.contains(s.substring(start, i)) && helper(s, set, memo, i)) {
                memo[start] = 1;
                return true;
            }
        }
        memo[start] = 0;
        return false;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>();
        for (String str : wordDict) {
            set.add(str);
        }

        int[] memo = new int[s.length()];
        Arrays.fill(memo, -1);
        return helper(s, set, memo, 0);
    }
}

Explanation 2

We can also use dynamic programming to solve this problem. Dynamic state is a one dimensioanl array dp, and it has length dp[s.length()+1]. It’s representd if the string[0:i) can be formed by the set or not.
Dynamic init is dp[0] = true because if the string is empty, then it is inside the set.
Dynamic function. For example, string = "1234567", if we want to find if the string end at 5 (12345) dp[5] is inside the set, previously, we should already finish dp[0], dp[1], dp[2], dp[3], dp[4], then we can loop through these dps, so if dp[0] is true and “12345” is inside the set, then dp[5] is true; else if dp[1] is true and “2345” is inside the set then dp[5] is true; else if dp[2] is true and “345” is inside the set, then we know dp[5] is true; In other word, we are using the previous dp[j] to count whether dp[i] is true where j is from 0 to i-1.
Dynamic result is the dp[dp.length()-1] which is the string from index 0 to the last character of the string.

Solution 2

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>();
        for (String str : wordDict) set.add(str);

        boolean[] dp = new boolean[s.length()+1];
        Arrays.fill(dp, false);
        dp[0] = true;

        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[dp.length-1];
    }
}