4747
4848<!-- 这里可写通用的实现逻辑 -->
4949
50+ ** 方法一：预处理 + DFS(回溯)**
51+
52+ 我们可以使用动态规划，预处理出字符串中的任意子串是否为回文串，即 $f[ i] [ j ] $ 表示子串 $s[ i..j] $ 是否为回文串。
53+
54+ 接下来，我们设计一个函数 $dfs(i)$，表示从字符串的第 $i$ 个字符开始，分割成若干回文串，当前分割方案为 $t$。
55+
56+ 如果 $i=|s|$，说明已经分割完成，我们将 $t$ 放入答案数组中，然后返回。
57+
58+ 否则，我们可以从 $i$ 开始，从小到大依次枚举结束位置 $j$，如果 $s[ i..j] $ 是回文串，那么就把 $s[ i..j] $ 加入到 $t$ 中，然后继续递归 $dfs(j+1)$，回溯的时候要弹出 $s[ i..j] $。
59+
60+ 时间复杂度 $O(n \times 2^n)$，空间复杂度 $O(n^2)$。其中 $n$ 是字符串的长度。
61+
5062<!-- tabs:start -->
5163
5264### ** Python3**
5668``` python
5769class Solution :
5870 def partition (self s : str ) -> List[List[str ]]:
59- ans = []
60- n = len (s)
61- dp = [[True ] * n for _ in range (n)]
62- for i in range (n - 1 , - 1 , - 1 ):
63- for j in range (i + 1 , n):
64- dp[i][j] = s[i] == s[j] and dp[i + 1 ][j - 1 ]
65-
66- def dfs (s , i , t ):
67- nonlocal n
71+ def dfs (i : int ):
6872 if i == n:
69- ans.append(t.copy() )
73+ ans.append(t[:] )
7074 return
7175 for j in range (i, n):
72- if dp [i][j]:
76+ if f [i][j]:
7377 t.append(s[i : j + 1 ])
74- dfs(s, j + 1 , t )
75- t.pop(- 1 )
78+ dfs(j + 1 )
79+ t.pop()
7680
77- dfs(s, 0 , [])
81+ n = len (s)
82+ f = [[True ] * n for _ in range (n)]
83+ for i in range (n - 1 , - 1 , - 1 ):
84+ for j in range (i + 1 , n):
85+ f[i][j] = s[i] == s[j] and f[i + 1 ][j - 1 ]
86+ ans = []
87+ t = []
88+ dfs(0 )
7889 return ans
7990```
8091
@@ -84,39 +95,37 @@ class Solution:
8495
8596``` java
8697class Solution {
87- private boolean [][] dp;
88- private List<List<String > > ans;
8998 private int n;
99+ private String s;
100+ private boolean [][] f;
101+ private List<String > t = new ArrayList<> ();
102+ private List<List<String > > ans = new ArrayList<> ();
90103
91- public String [][] partition (String s ) {
92- ans = new ArrayList<> ();
104+ public List<List<String > > partition (String s ) {
93105 n = s. length();
94- dp = new boolean [n][n];
106+ f = new boolean [n][n];
95107 for (int i = 0 ; i < n; ++ i) {
96- Arrays . fill(dp [i], true );
108+ Arrays . fill(f [i], true );
97109 }
98110 for (int i = n - 1 ; i >= 0 ; -- i) {
99111 for (int j = i + 1 ; j < n; ++ j) {
100- dp [i][j] = s. charAt(i) == s. charAt(j) && dp [i + 1 ][j - 1 ];
112+ f [i][j] = s. charAt(i) == s. charAt(j) && f [i + 1 ][j - 1 ];
101113 }
102114 }
103- dfs(s, 0 , new ArrayList<> ());
104- String [][] res = new String [ans. size()][];
105- for (int i = 0 ; i < ans. size(); ++ i) {
106- res[i] = ans. get(i). toArray(new String [0 ]);
107- }
108- return res;
115+ this . s = s;
116+ dfs(0 );
117+ return ans;
109118 }
110119
111- private void dfs (String s , int i , List< String > t ) {
112- if (i == n ) {
120+ private void dfs (int i ) {
121+ if (i == s . length() ) {
113122 ans. add(new ArrayList<> (t));
114123 return ;
115124 }
116125 for (int j = i; j < n; ++ j) {
117- if (dp [i][j]) {
126+ if (f [i][j]) {
118127 t. add(s. substring(i, j + 1 ));
119- dfs(s, j + 1 , t );
128+ dfs(j + 1 );
120129 t. remove(t. size() - 1 );
121130 }
122131 }
@@ -129,76 +138,147 @@ class Solution {
129138``` cpp
130139class Solution {
131140public:
132- vector<vector<bool >> dp;
133- vector<vector<string >> ans;
134- int n;
135-
136141 vector<vector<string >> partition(string s) {
137- n = s.size();
138- dp.assign(n, vector<bool>(n, true));
142+ int n = s.size();
143+ bool f[ n] [ n ] ;
144+ memset(f, true, sizeof(f));
139145 for (int i = n - 1; i >= 0; --i) {
140146 for (int j = i + 1; j < n; ++j) {
141- dp [i][j] = s[i] == s[j] && dp [i + 1][j - 1];
147+ f [ i] [ j ] = s[ i] == s[ j] && f [ i + 1] [ j - 1 ] ;
142148 }
143149 }
150+ vector<vector<string >> ans;
144151 vector<string > t;
145- dfs (s, 0, t);
146- return ans;
147- }
148-
149- void dfs(string& s, int i, vector<string> t) {
150- if (i == n) {
151- ans.push_back(t);
152- return;
153- }
154- for (int j = i; j < n; ++j) {
155- if (dp[i][j]) {
156- t.push_back(s.substr(i, j - i + 1));
157- dfs(s, j + 1, t);
158- t.pop_back();
152+ function<void(int)> dfs = [ &] (int i) {
153+ if (i == n) {
154+ ans.push_back(t);
155+ return;
159156 }
160- }
157+ for (int j = i; j < n; ++j) {
158+ if (f[ i] [ j ] ) {
159+ t.push_back(s.substr(i, j - i + 1));
160+ dfs(j + 1);
161+ t.pop_back();
162+ }
163+ }
164+ };
165+ dfs(0);
166+ return ans;
161167 }
162168};
163169```
164170
165171### **Go**
166172
167173```go
168- func partition(s string) [][]string {
174+ func partition(s string) (ans [][]string) {
169175 n := len(s)
170- dp := make([][]bool, n)
171- var ans [][]string
172- for i := 0; i < n; i++ {
173- dp[i] = make([]bool, n)
174- for j := 0; j < n; j++ {
175- dp[i][j] = true
176+ f := make([][]bool, n)
177+ for i := range f {
178+ f[i] = make([]bool, n)
179+ for j := range f[i] {
180+ f[i][j] = true
176181 }
177182 }
178183 for i := n - 1; i >= 0; i-- {
179184 for j := i + 1; j < n; j++ {
180- dp [i][j] = s[i] == s[j] && dp [i+1][j-1]
185+ f [i][j] = s[i] == s[j] && f [i+1][j-1]
181186 }
182187 }
183-
184- var dfs func(s string, i int, t []string )
185- dfs = func(s string, i int, t []string ) {
188+ t := []string{}
189+ var dfs func(int)
190+ dfs = func(i int) {
186191 if i == n {
187192 ans = append(ans, append([]string(nil), t...))
188193 return
189194 }
190195 for j := i; j < n; j++ {
191- if dp [i][j] {
196+ if f [i][j] {
192197 t = append(t, s[i:j+1])
193- dfs(s, j+1, t )
198+ dfs(j + 1 )
194199 t = t[:len(t)-1]
195200 }
196201 }
197202 }
203+ dfs(0)
204+ return
205+ }
206+ ```
207+
208+ ### ** TypeScript**
209+
210+ ``` ts
211+ function partition(s : string ): string [][] {
212+ const = s .length ;
213+ const : boolean [][] = new Array (n )
214+ .fill (0 )
215+ .map (() => new Array (n ).fill (true ));
216+ for (let i = n - 1 ; i >= 0 ; -- i ) {
217+ for (let j = i + 1 ; j < n ; ++ j ) {
218+ f [i ][j ] = s [i ] === s [j ] && f [i + 1 ][j - 1 ];
219+ }
220+ }
221+ const : string [][] = [];
222+ const : string [] = [];
223+ const = (i : number ) => {
224+ if (i === n ) {
225+ ans .push (t .slice ());
226+ return ;
227+ }
228+ for (let j = i ; j < n ; ++ j ) {
229+ if (f [i ][j ]) {
230+ t .push (s .slice (i , j + 1 ));
231+ dfs (j + 1 );
232+ t .pop ();
233+ }
234+ }
235+ };
236+ dfs (0 );
237+ return ans ;
238+ }
239+ ```
240+
241+ ### ** C#**
242+
243+ ``` cs
244+ public class Solution {
245+ private int n ;
246+ private string s ;
247+ private bool [,] f ;
248+ private IList <IList <string >> ans = new List <IList <string >>();
249+ private IList <string > t = new List <string >();
250+
251+ public IList <IList <string >> Partition (string s ) {
252+ n = s .Length ;
253+ this .s = s ;
254+ f = new bool [n , n ];
255+ for (int i = 0 ; i < n ; ++ i ) {
256+ for (int j = 0 ; j <= i ; ++ j ) {
257+ f [i , j ] = true ;
258+ }
259+ }
260+ for (int i = n - 1 ; i >= 0 ; -- i ) {
261+ for (int j = i + 1 ; j < n ; ++ j ) {
262+ f [i , j ] = s [i ] == s [j ] && f [i + 1 , j - 1 ];
263+ }
264+ }
265+ dfs (0 );
266+ return ans ;
267+ }
198268
199- var t []string
200- dfs(s, 0, t)
201- return ans
269+ private void dfs (int i ) {
270+ if (i == n ) {
271+ ans .Add (new List <string >(t ));
272+ return ;
273+ }
274+ for (int j = i ; j < n ; ++ j ) {
275+ if (f [i , j ]) {
276+ t .Add (s .Substring (i , j + 1 - i ));
277+ dfs (j + 1 );
278+ t .RemoveAt (t .Count - 1 );
279+ }
280+ }
281+ }
202282}
203283```
204284
0 commit comments