-
Notifications
You must be signed in to change notification settings - Fork 0
/
DistinctSubsequence.cpp
69 lines (60 loc) · 1.64 KB
/
DistinctSubsequence.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
* DistinctSubsequence.cpp
*
* Created on: Jun 29, 2016
* Author: gokul
*/
#include <string>
#include <unordered_map>
#include <iostream>
using namespace std;
class Solution {
unordered_map<uint64_t, uint64_t> _counts;
public:
inline uint64_t indexHash(uint32_t sindex, uint32_t tindex)
{
return ((uint64_t)sindex << 32 | tindex);
}
uint64_t countDistinctSubSequence(const string& s, const string& t, uint32_t sindex, uint32_t tindex)
{
auto slen = s.length();
auto tlen = t.length();
if (sindex >= slen || tindex >= tlen) {
return 0;
}
uint64_t hashVal = indexHash(sindex, tindex);
if (tlen-tindex > slen - sindex) {
_counts[hashVal] = 0;
return 0;
}
unordered_map<uint64_t, uint64_t>::const_iterator it = _counts.find(hashVal);
if (it != _counts.end()) {
return it->second;
}
auto searchChar = t[tindex];
auto numSeq = 0;
size_t i = sindex;
while (i < slen) {
i = s.find(searchChar, i);
if (i == string::npos) {
break;
}
if (tindex == tlen - 1) {
numSeq++;
} else {
numSeq += countDistinctSubSequence(s, t, i + 1, tindex+1);
}
++i;
}
_counts[hashVal] = numSeq;
return numSeq;
}
};
int main(int argc, char** argv)
{
std::string s = "ccc";
std::string t = "c";
Solution sol;
cout << "Total = " << sol.countDistinctSubSequence(s, t, 0, 0) << endl;
return 0;
}