Clean c++ O(n) space dp solution


  • 1

    Same idea with wildcard matching.

    int numDistinct(string s, string t) {
        int ssize = s.size(), tsize = t.size();
        vector<int> match(tsize + 1);
        match[0] = 1;
        for (int i = 0; i < ssize; i++) {
            int prev = match[0];
            for (int j = 0; j < tsize; j++) {
                int temp = match[j + 1];
                match[j + 1] += s[i] == t[j] ? prev : 0;
                prev = temp;
            }
        }
        return match[tsize];
    }
    

  • 0

    Nice Solution!


Log in to reply
 

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