blob: e553a5eaa2b262217c2b16e628cb32b6123698dc (
plain)
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
|
/*
Challenge 099
TASK #2 � Unique Sub-sequence
Submitted by : Mohammad S Anwar
You are given two strings $S and $T.
Write a script to find out count of different unique sub-sequences matching
$T without changing the position of characters.
Example 1:
Input : $S = "littleit', $T = 'lit'
Output : 5
1: [lit] tleit
2: [li] t[t] leit
3: [li] ttlei[t]
4: litt[l] e[it]
5: [l] ittle[it]
Example 2:
Input : $S = "london', $T = 'lon'
Output : 3
1: [lon] don
2: [lo] ndo[n]
3: [l] ond[on]
*/
#include <iostream>
int count_subsequences(const char* s, const char* t) {
while (true) {
if (!*t) // t is empty, matched
return 1;
else if (!*s) // s is empty, did not match
return 0;
else if (*s == *t) { // same char, check two paths matching and not matching
int matching = count_subsequences(s + 1, t + 1);
int not_matching = count_subsequences(s + 1, t);
return matching + not_matching;
}
else // different char, keep pattern
s++;
}
}
int main(int argc, char* argv[]) {
if (argc == 3)
std::cout << count_subsequences(argv[1], argv[2]) << std::endl;
else {
std::cerr << "Usage: ch-2 string test" << std::endl;
return EXIT_FAILURE;
}
}
|
