scrabmle string

Posted on |

scramble string at leetCode 87. sol: get all possible scrambled strings of s1, then compare if s2 is in it.

for 1-char:   scramble("a") --> "a" 
    for 2-chars :  scramble("ab") --> "ba"  
for 3-chars:  scramble("abc") --> "bac", "cba",  "acb", "cba"      for 4-chars:   scramble("abcd") -->  (a | bcd) + (ab | cd) +  (abc | d) 
for 5-chars:  scramble("abcde") --> (a | bcde) +  (ab | cde) +  (abc |  de) + (abcd | e)

from the enumaration, there is always a left-substring and a right-substring, and recursive in each substring. consider the push_back order, there are two: left->\right and right->\left at each two slibings.

additional routines: how to do substring join and how to delete duplicate string from string-vector.

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
 string join(string& sub1, string& sub2)
 {
	 string res; 
	 res.reserve(sub1.size() + sub2.size());
	 
	 string::iterator it;
	 
	 for(it = sub1.begin(); it != sub1.end(); it++)
		 res.push_back(*it);
	 
	 for(it = sub2.begin(); it != sub2.end(); it++)
		 res.push_back(*it);
	 
	 return res;
 }
 
 //TODO:  keep in mind the transfer function, and how to design it  
 vector<string>  scramble(string& s)
 {
	 string  ls, rs; 
	 vector<string> vls, vrs, vcurs; 
	 
	 if(s.size() == 1)
	 {
		 vcurs.push_back(s); 
		 return vcurs; 
	 }
	 
	 for(int i=1; i<s.size(); i++)
	 {
		 ls = s.substr(0, i);
		 rs = s.substr(i, s.size()); 
		 vls = scramble(ls);
		 vrs = scramble(rs); 		 
		 
		 for(int m=0; m< vls.size(); m++)
			 for(int n=0; n < vrs.size(); n++)
			 {				 
				 vcurs.push_back(join(vls[m], vrs[n])); 
				 vcurs.push_back(join(vrs[n], vls[m])); 			 
			 }
	 }
/*how to delete duplicated string from vector<string> */ 	 
	 std::sort(vcurs.begin(), vcurs.end()); 
	 vcurs.erase( std::unique(vcurs.begin(), vcurs.end()), vcurs.end()); 
	 return vcurs; 
 } 
int main()
{
	string s1 = "abcd" ;
	vector<string> outs = scramble(s1); 
	for(int i=0; i<outs.size(); i++)
		cout << outs[i] << endl; 
	return 0;
}

How to write a completed code, meaning, always take care the boundaries correctly, no missing situations. It’s easy to start from scratch and achieve somewhere, but hard to be completed.