when pure loop doesn't work out

Posted on |

leetCode 115: given a string S and a string T, count the number of distinct subsequences of S which equals T.

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
   ^  ^^
babgbag
     ^^^

first thought

for each alpha in T, traversing S, find a match, return; then move forward for next alpha in T and traversing S again,

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
int sol(string& s1,  string& s2)
{
 string::iterator sit1, sit2, nait; 
 string notagain; 
 int count=0;	 
for(nait = s2.begin(); nait != s2.end(); nait++)
{
	notagain.push_back(*nait);
	sit1 =  s1.begin(); 
	sit1_last = s1.begin(); 
	
	while( sit1 != s1.end())
	{	 
		for(sit2=s2.begin(); sit2 != s2.end(), sit1 != s1.end(); sit1++)
		{
			if(*sit1 == *sit2)
			{
				tmp.push_back(*sit2);
				sit2++; 
			}
		 
			if(tmp.compare(s2) == 0)
			{
				count++;
				break;
			}
		}
		
		sit1 = st1_last++;
	}	
}
}

this is a failed trail. Since this kind of problem really can’t be solved by purely nested for-loop. think about, at the last level (traverse S to get g), there needs one for-loop, then the previous level or the level above (traverse S to get a) needs another loop. and each “a” needs one for-loop to traverse all possible “g” in S again. and the top level (travers S to get “b”) is another for-loop, and each “b” need another for-loop to traverse “a”. and this is only three levels (b->a->g)

basically if implementing tree traversing with for-loop, since tree structure has many branches to the end, since even each sub-branch needs a for-loop, there will be exponent disaster of for-loop to cover all branches.

second thoughts

what’s the different mindset? recursive. when dealing with many-branches-travsersing (e.g. a tree strucutre), recursive is nature to think. since recursive only consider the neighbor two level branches.

for this example, inside each recursive need a for-loop to catch all possible positions of the satisfied character, and stack is need to, when visiting a new character from T need poush, and when find out a T, then need to pop out the last character.

during breadth traversing tree, either using a pure recursive or using stack with a while-loop. but here it needs a for-loop and stack inside each recursive. (a little complex)

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
void rec(string& S, string& T, string::iterator tc, std::stack<char> ss,  int& nums )
{
	if(tc == T.end())
		return ;
	
	for(int i= 0; i<S.size(); i++)
	{
		if(S[i] == *tc)
		{
			ss.push(*tc);
			if(ss.size() != T.size())
			{
				string cur_s = S.substr(i+1); 
				rec(cur_s, T,  ++tc,  ss, nums);
				--tc; 
				ss.pop();
			}else
			{
				cout << "found one\n" ; 
				nums++; 
				ss.pop(); 
			}
		}
	}
}
int sol(string& S,  string& T)
{
	string::iterator tit = T.begin();
	std::stack<char>  ss ;
	int nums =0; 
	rec(S, T, tit, ss, nums); 
	
	return nums; 
}

TODO: there suppose be a general pattern for this kind of problem.

third thoughts

if the problem is too complex to handle at first, more memory always make it looks simple, using containers to split the content. with 2 for-loops to create #num of buckets to store positions of each alphaet in T

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int sol(string& s1,  string& s2)
{
	int length =  s2.size(); 
	std::map<char, vector<int>>  smap; 
	std::vector<int> pos; 
	string::iterator sit; 
	char alpha ; 
	for(i=0; i<s2.size(); i++)
	{
		alpha = s2[i]; 
		int i=0; 
		pos.clear(); 
		for(sit = s1.begin(); sit != s1.end(); sit++)
		{
			if( alpha == *sit)
			{
				pos.push_back(i++);
			}
		}
		smap.insert(std::pair<char, vector<int>>(alpha, pos);
	}
b 0, 2, 4
a 1, 5
g 3, 6

after get the map, then play the combinations games. that’s actually still a recursive problem.