public boolean wordBreak3(String s, Set<String> dict) {
        boolean[] memo = new boolean[s.length() + 1];
        memo[0] = true;
        for(int i = 0; i < s.length(); i++){
            if(memo[i]){
                for(String word : dict){
                    if(word.length() + i <= s.length()){
                        String sub = s.substring(i, i + word.length());
                        if(sub.equals(word)){
                            memo[i + word.length()] = true;
                        }
                    }
                }
            }
        }
        return memo[s.length()];
    }