Alternative solution without using DP. Space complexity O(m). Time complexity O(m * n)


  • -2
    A
    class Solution {
    public:
        int numDistinct(string S, string T) {
            /* prefix_map maps each character of string T to a prefix in string T 
             * that this character can extend. For example for T = "rabbit" mapping 
             * will be {r -> "", a -> "r", b -> "ra, rab", i -> "rabb", t -> "rabbi"} */
            unordered_multimap<char, string> prefix_map;
            for (int i = 0; i < T.size(); ++i)
                prefix_map.insert(make_pair(T[i], T.substr(0, i)));
                
            /* prefix_count stores number of prefixes of T found so far. Initially
             * it contains all zeros */
            unordered_map<string, int> prefix_count;
            for (int i = 0; i < T.size(); ++i)
                prefix_count[T.substr(0, i + 1)] = 0;
                
            /* for each character c in string S we use prefix_map to found which
             * prefixes can be extended using c and update prefix_count accordingly */
            for (int i = 0; i < S.size(); ++i)
            {
                auto range = prefix_map.equal_range(S[i]);
                for (auto it = range.first; it != range.second; ++it)
                {
                    string prefix = it->second;
                    string cur = prefix + S[i];
    
                    if (prefix.empty())
                        prefix_count[cur] += 1;
                    else
                        prefix_count[cur] += prefix_count[prefix];
                }
            }
            
            return prefix_count[T];
        }
    };

  • 1
    A

    I think it's still DP. prefix_count is restoring the information before, which is just DP...


  • -1
    J

    prefix_ma needs O(N^2) space (if T is length N).


  • 0
    J

    Failed when S="eee",T="eee". This algorithm failed when there are successive characters in T.


Log in to reply
 

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