Distinct Subsequences

A subsequence is a sequence obtained from another by the exclusion of a number of elements.
Note : The relative order of elements in a subsequence remains the same as that of the original sequence.

Example of a subsequence in a given sequence
Sequence: [ย S,ย U,ย N,ย D,ย A,ย Y]
Subsequence 1: [ย S,ย U,ย Nย ]
Subsequence 2: [ย S,ย A,ย Yย ]
Subsequence 3: [ย D,ย A,ย Yย ]




Finding number of distinct subsequences in a source string matching the target string.

#include<iostream>
#include<map>
#include<string>
#include<vector>

using namespace std;

class DistinctSubsequences {

    public:
    map<pair<string,string>, int> table;

    int NumDistinct (string src, string target) {

        if (src.size() < target.size()) {
            return 0;
        }

        if (table.find (make_pair (src, target)) != table.end()) {
            return table[make_pair (src, target)];
        }

        int ways = 0;

        if (src.empty() && target.empty()) {
            return 1;
        } else if (src.empty() == false and target.empty() == true) {
            return 1;
        } else if (src.empty() == true and target.empty() == false) {
            return 0;
        } else if (src.at(0) == target.at(0)) {
            ways += NumDistinct (src.substr(1), target.substr(1));
            ways += NumDistinct (src.substr(1), target);
        } else {
            ways += NumDistinct (src.substr(1), target);
        }

        table[make_pair(src, target)] = ways;
        return ways;
    }
};

int main() {

    DistinctSubsequences ds;

    vector<string> src = { "abab", "babgbag", "rabbbit", "sunnylion", "willbbertt" };
    vector<string> target = { "ab", "bag", "rabbit", "sun", "wilbert" };

    for (int i=0; i<src.size(); i++) {
        cout << "Number of distinct subsequences of " << src[i] << " which equal " << target[i] << " : " << ds.NumDistinct(src[i], target[i]) << endl;
    }
    return 0;
}

Output

Number of distinct subsequences of abab which equal ab : 3
Number of distinct subsequences of babgbag which equal bag : 5
Number of distinct subsequences of rabbbit which equal rabbit : 3
Number of distinct subsequences of sunnylion which equal sun : 3
Number of distinct subsequences of willbbertt which equal wilbert : 8



Copyright (c) 2019-2022, Algotree.org.
All rights reserved.