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
|
#!/usr/bin/gawk
# Challenge 099
#
# TASK #2 > Unique Subsequence
# Submitted by: Mohammad S Anwar
# You are given two strings $S and $T.
#
# Write a script to find out count of different unique subsequences 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]
function count_subsequences(s, t) {
while (1) {
if (t=="") { # t is empty, matched
return 1;
}
else if (s=="") { # s is empty, did not match
return 0;
}
else if (substr(s,1,1) == substr(t,1,1)) { # same char,
# check two paths matching
# and not matching
return count_subsequences(substr(s,2), substr(t,2)) \
+ count_subsequences(substr(s,2), t);
}
else { # different char, keep pattern
s = substr(s,2);
}
}
}
BEGIN {
print count_subsequences(ARGV[1], ARGV[2]);
exit 0;
}
|
