Word Break leetcode

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

state: f[i]表示前i个字符是否可以完美切分

function: f[i] = f[j] +(substring[j+1 --> i]是dict中单词)

initial： f[0] = true

return:f[s.length]
假设总共有n个字符串，并且字典是用HashSet来维护，那么总共需要n次迭代，每次迭代需要一个取子串的O(i)操作，然后检测i个子串，而检测是constant操作。所以总的时间复杂度是O(n^2)（i的累加仍然是n^2量级），而空间复杂度则是字符串的数量，即O(n)。

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if (s == null || s.length() == 0) {
            return false;
        }
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j <i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j,i))) {//substring是左闭右开的所以表示j+1 到i字符
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
        
    }
}