public boolean check(String s, int begin, HashSet<String> wordSet) {
        if (begin >= s.length()) {
            return true;
        }

        for (int i = begin; i < s.length(); ++i) {
            String str = s.substring(begin, i + 1);
            if (!wordSet.contains(str))
                continue;
            if (check(s, i + 1, wordSet))
                return true;
        }
        return false;
    }