Какова временная сложность этой проблемы L C

Question

Может ли кто-нибудь провести меня через анализ сложности времени для этой проблемы? https://leetcode.com/problems/palindrome-partitioning/

У меня было решение с использованием DFS + backtracking + DP, как показано ниже, я думаю, с точки зрения сложности времени, это сводится к количеству разделов, которые вы можете иметь для сусла случай, но изо всех сил пытался выяснить, что это такое.

class Solution {
public:
    vector<string> cur;
    vector<vector<string>> ans;
    vector<vector<bool>> isPalindrome;
    unordered_map<int,vector<int>> pairs;

    vector<vector<string>> partition(string s) {
        isPalindrome.resize(s.length(),vector<bool>(s.length(),false));
        buildPalindromePairs(s);
        backtracking(s,0);
        return ans;
    }

    void buildPalindromePairs(string s)
    {
        for(int i=0;i<s.length();++i)
        {
            for(int j=i;j>=0;j--)
            {
                if(i==j) 
                    isPalindrome[j][i]=true;
                else if(j==i-1 && s[j]==s[i]) 
                    isPalindrome[j][i]=true;
                else if(s[j]==s[i] && isPalindrome[j+1][i-1])
                    isPalindrome[j][i]=true;

                if(isPalindrome[j][i])
                    pairs[j].push_back(i);
            }
        }
    }

    void backtracking(string s, int start)
    {
        if(start==s.length()) 
        {
            ans.push_back(cur);
            return;
        }

        for(auto end:pairs[start])
        {
            cur.push_back(s.substr(start, end-start+1));
            backtracking(s,end+1);
            cur.pop_back();
        }
    }
};

Answer 1

Метод isPalindrome() может быть решен в O(n).

Метод buildPalindromePairs(string s) равен O(n^2), как в случае вложенного для l oop.

Метод void backtracking(string s, int start) равен O(2^(n - 1)), так как каждый символ вы можете выбирать или не выбирать. Таким образом, у каждого персонажа есть 2 варианта. И поэтому n символы могут представлять 2^n параметры в идеале (2^(n-1)), так как в идеале должен быть один символ.

Общая сложность O(2^n).