# Word Break III

{% tabs %}
{% tab title="Java" %}

```java
public class Solution {
    /*
     * @param : A string
     * @param : A set of word
     * @return: the number of possible sentences.
     */
    public int wordBreak3(String s, Set<String> dict) {
        int n = s.length();
        String lowerS = s.toLowerCase();
        
        Set<String> lowerDict = new HashSet<String>();
        for(String str : dict) {
            lowerDict.add(str.toLowerCase());
        }
        int[][] dp = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = i; j < n;j++){
                String sub = lowerS.substring(i, j + 1);
                if(lowerDict.contains(sub)){
                    dp[i][j] = 1;
                }
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){
                for(int k = i; k < j; k++){
                    dp[i][j] += (dp[i][k] * dp[k + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
}
```

{% endtab %}
{% endtabs %}

![](https://2784211123-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M-ELB26IpzCEJWSDi0m%2F-M-ELbsic2B8wwsarT-C%2F-M-EMqc6UhBUlpM3zyHy%2F1580805867266.jpg?alt=media\&token=11a20b67-9e32-4c02-bf02-c405dac8ef0f)