-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
38 lines (36 loc) · 914 Bytes
/
Solution.cs
File metadata and controls
38 lines (36 loc) · 914 Bytes
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
public class Solution
{
public IList<IList<string>> Partition(string s)
{
IList<IList<string>> ret = [];
BackTracking(ret, 0, s.Length, s, []);
return ret;
}
void BackTracking(IList<IList<string>> ret, int pos, int n, string s, IList<string> curr)
{
if (pos >= n)
{
ret.Add([.. curr]);
return;
}
for (int i = pos; i < n; i++)
{
string candidate = s[pos..(i + 1)];
if (IsPalindrome(candidate))
{
curr.Add(candidate);
BackTracking(ret, i + 1, n, s, curr);
curr.RemoveAt(curr.Count - 1);
}
}
}
bool IsPalindrome(string s)
{
int n = s.Length;
for (int i = 0; i <= n / 2; i++)
{
if (s[i] != s[n - 1 - i]) return false;
}
return true;
}
}