一次过
1
class
Solution {
2
public
:
3
bool
check(
string
s) {
4
for
(
int
i =
0
; i < s.size(); i++
) {
5
if
(s[i] != s[s.size()-
1
-i])
return
false
;
6
}
7
return
true
;
8
}
9
void
dfs(vector<vector<
string
>> &ret, vector<
string
> &retin,
string
s,
int
beg,
int
size) {
10
if
(beg ==
size) ret.push_back(retin);
11
for
(
int
i =
1
; i <= size-beg; i++
) {
12
if
(check(s.substr(beg, i))) {
13
retin.push_back(s.substr(beg, i));
14
dfs(ret, retin, s, beg+
i, size);
15
retin.pop_back();
16
}
17
}
18
}
19
vector<vector<
string
>> partition(
string
s) {
20
//
Start typing your C/C++ solution below
21
//
DO NOT write int main() function
22
vector<vector<
string
>>
ret;
23
vector<
string
>
retin;
24
dfs(ret, retin, s,
0
, s.size());
25
return
ret;
26
}
27
};
C#
1
public
class
Solution {
2
public
List<List<
string
>> Partition(
string
s) {
3
List<List<
string
>> ans =
new
List<List<
string
>>
();
4
List<
string
> tmp =
new
List<
string
>
();
5
dfs(
ref
ans,
ref
tmp, s,
0
, s.Length);
6
return
ans;
7
}
8
public
void
dfs(
ref
List<List<
string
>> ans,
ref
List<
string
> tmp,
string
s,
int
beg,
int
size) {
9
if
(beg ==
size) {
10
List<
string
> local =
new
List<
string
>
(tmp.ToArray());
11
ans.Add(local);
12
}
13
for
(
int
i =
1
; i <= size - beg; i++
) {
14
if
(check(s.Substring(beg, i))) {
15
tmp.Add(s.Substring(beg, i));
16
dfs(
ref
ans,
ref
tmp, s, beg+
i, size);
17
tmp.RemoveAt(tmp.Count-
1
);
18
}
19
}
20
}
21
public
bool
check(
string
s) {
22
for
(
int
i =
0
; i < s.Length; i++
) {
23
if
(s[i] != s[s.Length-
1
-i])
return
false
;
24
}
25
return
true
;
26
}
27
}
