Какова большая О этого алгоритма динамического программирования?

Question

Вот вопрос динамического программирования: (leetcode 139) Если задана непустая строка s и словарь wordDict, содержащий список непустых слов, определить, можно ли s сегментировать в пробел.разделенная последовательность из одного или нескольких слов словаря.

Примечание:

Одно и то же слово в словаре может быть многократно использовано в сегментации.Вы можете предположить, что словарь не содержит повторяющихся слов.

И мое решение:

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>();
        Set<String> failed = new HashSet<>();
        Set<String> success = new HashSet<>();
        int maxLength = 0;
        int[] letters = new int[256];
        for(String word: wordDict){
            maxLength = Math.max(maxLength,word.length());
            for(int i = 0; i< word.length(); i++){
                letters[word.charAt(i)] = 1;
            }
            set.add(word);
        }

        for(int i = 0; i< s.length(); i++){
            if(letters[s.charAt(i)]==0)
                return false;
        }
        return dp(s,set,maxLength,failed,success);

    }

    public boolean dp(String s, Set<String> set,int max,Set<String> failed, Set<String> success){
        // base case 
        if(set.contains(s)){
            success.add(s);
            return true;
        }
        if(success.contains(s)){
            return true;
        }   // do I have to overload the comperator?

        if(failed.contains(s))
            return false;
        // self call
        for(int i = Math.min(max,s.length())-1; i>=0 ; i--){
            if(set.contains(s.substring(0,i+1))){
                String sub= s.substring(i+1,s.length());
                if(success.contains(sub)||dp(sub,set,max,failed,success)){
                    success.add(s);
                    return true;
                }

            }
        }
        failed.add(s);
        // return
        return false;
    }
}

Основная идея моего решения - 1. проверьте, может ли строка быть AWordInTheDict + rest;если так, проверьте, может ли остальная часть быть той же самой структурой рекурсивно.2. сохранить успешный набор и неудачный набор, чтобы избежать повторяющихся рекурсивных вызовов. Мой вопрос: Несмотря на то, что это решение прошло все тестовые случаи и составляет более 94% других решений, я не смог рассчитать временную сложность этого решения.Я думаю, что без успеха и неудачного набора решение будет работать на экспоненциальном уровне времени.Я думаю, что успех и неудача определенно снизили экспоненциальный уровень, но я не знаю, насколько именно он уменьшается.Так в чем же заключается большое значение этого решения?И еще, есть ли среднее время выполнения (дельта O) для решения?