Give a dictionary of words and a sentence with all whitespace removed, return the number of sentences you can form by inserting whitespaces to the sentence so that each word can be found in the dictionary.

Have you met this question in a real interview?

Yes

Example

Given a StringCatMat
Given a dictionary["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"]
return3

we can form 3 sentences, as follows:
CatMat = Cat Mat
CatMat = Ca tM at
CatMat = C at Mat

1. dfs (need to make all word small case)

public class Solution {
    /*
     * @param : A string
     * @param : A set of word
     * @return: the number of possible sentences.
     */
    private int ans = 0;
    public int wordBreak3(String s, Set<String> dict) {
        // Write your code here
        if (s == null || s.length() == 0 || dict == null || dict.size() == 0) {
            return ans;
        }

        dfs(0, s, dict);

        return ans;

    }

    private void dfs(int startIndex, String s, Set<String> dict) {
        if (startIndex >= s.length()) {
            ans++;
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            String cur = s.substring(startIndex, i + 1);
            if (!dict.contains(cur)) {
                continue;
            }
            dfs(i + 1, s, dict);
        }

    }
}