[C++] My primary O(N*M) DP solution using O(N*M) space (poor math)


  • 0
    J

    Though I'm not very good at math, I finally struggled to get AC.

    class Solution {
    public:
        typedef unordered_map<int*, int> Cache;
    
        int numDistinct(string S, string T) {
            if (T.empty()) return 1;
            if (S.empty() || S.length() < T.length()) return 0;
            // collect indexes for each char of T in S
            vector<vector<int>> indexes(T.length());
            for (int i = 0; i < S.length(); i++) {
                for (int j = 0; j < T.length(); j++) {
                    if (S[i] == T[j]) {
                        indexes[j].push_back(i);
                    }
                }
            }
            Cache cache;
            // calculate all possible ways to get the next char of T recursively
            return countDistinct(indexes, 0, -1, cache);
        }
        int countDistinct(vector<vector<int>> &indexes, int n, int limit, Cache &cache) {
            vector<int> &index = indexes[n];
            int sum = 0;
            for (int i = index.size() - 1; i >= 0; i--) {
                if (index[i] <= limit) break;  // the index of the next char must be bigger
                if (n + 1 < indexes.size()) {
                    auto it = cache.find(&index[i]);
                    if (it == cache.end()) {
                        int num = countDistinct(indexes, n + 1, index[i], cache);
                        cache[&index[i]] = num;
                        sum += num;
                    } else {
                        sum += it->second;
                    }
                } else {
                    sum++;
                }
            }
            return sum;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.