public boolean wordBreak(String s, Set<String> dict) {
        if (s.length() == 0) {
            return false;
        }

        boolean[] possiblity = new boolean[s.length()];

        for (int i = 0; i < s.length(); i++) {
            for (String word : dict) {
                if (i < word.length() - 1) {
                    continue;
                }
                if ((i - word.length() == -1 || possiblity[i - word.length()]) &&
                        s.substring(i + 1 - word.length(), i + 1 - word.length() + word.length()).equals(word)) {
                    possiblity[i] = true;
                }
            }
        }


        return possiblity[s.length() - 1];

    }