public boolean wordBreak4(String s, Set<String> dict) {
        int len = s.length();
        boolean[] memo = new boolean[len + 1];
        memo[0] = true;
        for(int i = 1; i <= len; i++){
            for(int j = 0; j < i; j++){
                if(memo[j] && dict.contains(s.substring(j, i))){
                    memo[i] = true;
                    break;
                }
            }
        }
        return memo[len];
    }