public boolean wordSegmentation(String s, Set<String> dict) {
        // write your code here  
        if (s == null || s.length() == 0){
            return true;
        }
        
        boolean[] canSeg = new boolean[s.length()];
        
        canSeg[0] = dict.contains(Character.toString(s.charAt(0)));
        
        for (int i = 1; i < s.length(); i++){
            canSeg[i] = false;
            if (dict.contains(s.substring(0, i + 1))){
                canSeg[i] = true;
                continue;
            }
            
            for (int j = 1; j <= i; j++){
                if (!canSeg[i - j]){
                    continue;
                }
                String sub = s.substring(i - j + 1, i + 1);
                if (dict.contains(sub)){
                    canSeg[i] = true;
                    break;
                } 
            }
        }
        
        return canSeg[s.length() - 1];
    }