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(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;
}
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> */
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.
近期评论