本节内容
- 39. 组合总和
- 40.组合总和II
- 131.分割回文串
39. 组合总和※
建议：本题是 集合里元素可以用无数次，那么和组合问题的差别 其实仅在于 startIndex上的控制
题目链接： https://leetcode.cn/problems/combination-sum/
文章讲解： https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html
视频讲解： https://www.bilibili.com/video/BV1KT4y1M7HJ
题目分析
方案一
先将原始的数组进行排序，排序完成之后在进行相关的操作，为了防止以下的问题：
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
| class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
backtracking(candidates,target, 0, 0, new ArrayList<>(), result);
return result;
}
private void backtracking(int[] candidates, int target, int start, int sum, List<Integer> temp, List<List<Integer>> result) {
if (target == sum) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = start; i < candidates.length; i++) {
if (sum + candidates[i] > target) return;
temp.add(candidates[i]);
backtracking(candidates, target, i, sum + candidates[i], temp, result);
temp.remove(temp.size() - 1);
}
}
}
|
结果
解答成功:
执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:42.5 MB,击败了62.67% 的Java用户
分析
时间复杂度：
O( n * 2^n )
空间复杂度：
O( target )
代码随想录
https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html
思路
本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。
本题搜索的过程抽象成树形结构如下：
注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！
回溯三部曲
这里依然是定义两个全局变量，二维数组result存放结果集，数组path存放符合条件的结果。（这两个变量可以作为函数参数传入）
首先是题目中给出的参数，集合candidates, 和目标值target。
此外还定义了int型的sum变量来统计单一结果path里的总和，其实这个sum也可以不用，用target做相应的减法就可以了，最后如何target==0就说明找到符合的结果了，但为了代码逻辑清晰，我依然用了sum。
本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？
如果是一个集合来求组合的话，就需要startIndex；如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex。
注意以上我只是说求组合的情况，如果是排列问题，又是另一套分析的套路，后面我再讲解排列的时候就重点介绍。
代码如下：
1
2
3
| vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex)
|
在如下树形结构中：
从叶子节点可以清晰看到，终止只有两种情况，sum大于target和sum等于target。
sum等于target的时候，需要收集结果，代码如下：
1
2
3
4
5
6
7
| if (sum > target) {
return;
}
if (sum == target) {
result.push_back(path);
return;
}
|
单层for循环依然是从startIndex开始，搜索candidates集合。
如何重复选取呢，看代码，注释部分：
1
2
3
4
5
6
7
| for (int i = startIndex; i < candidates.size(); i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i);
sum -= candidates[i];
path.pop_back();
}
|
剪枝优化
在这个树形结构中：
以及上面的版本一的代码大家可以看到，对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。
其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。
那么可以在for循环的搜索范围上做做文章了。
对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。
如图：
for循环剪枝代码如下：
1
| for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)
|
- 时间复杂度: O(n * 2^n)，注意这只是复杂度的上界，因为剪枝的存在，真实的时间复杂度远小于此
- 空间复杂度: O(target)
代码实现
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
|
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates);
backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
return res;
}
public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = idx; i < candidates.length; i++) {
if (sum + candidates[i] > target) break;
path.add(candidates[i]);
backtracking(res, path, candidates, target, sum + candidates[i], i);
path.remove(path.size() - 1);
}
}
}
|
40.组合总和II※
建议：本题开始涉及到一个问题了：去重。
注意题目中给我们 集合是有重复元素的，那么求出来的 组合有可能重复，但题目要求不能有重复组合。
题目链接： https://leetcode.cn/problems/combination-sum-ii/
文章讲解： https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html
视频讲解： https://www.bilibili.com/video/BV12V4y1V73A
题目分析
方案一
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
| class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
backtracking(candidates, target, 0, 0, new ArrayList<>(), result);
return result;
}
private void backtracking(int[] candidates, int target, int start, int sum, List<Integer> temp, List<List<Integer>> result) {
if (target == sum) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = start; i < candidates.length; i++) {
if (sum + candidates[i] > target) return;
temp.add(candidates[i]);
backtracking(candidates, target, i + 1, sum + candidates[i], temp, result);
while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {
i++;
}
temp.remove(temp.size() - 1);
}
}
}
|
结果
解答成功:
执行耗时:2 ms,击败了99.61% 的Java用户
内存消耗:41.4 MB,击败了74.66% 的Java用户
分析
时间复杂度：
O( n * 2^n )
空间复杂度：
O( n )
代码随想录
https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html
思路
- 本题candidates 中的每个数字在每个组合中只能使用一次。
- 本题数组candidates的元素是有重复的。
解集不能包含重复的组合。
本题的难点在于：集合（数组candidates）有重复元素，但还不能有重复的组合。
一些同学可能想了：我把所有组合求出来，再用set或者map去重，这么做很容易超时！
所以要在搜索的过程中就去掉重复组合。
很多同学在去重的问题上想不明白，其实很多题解也没有讲清楚，反正代码是能过的，感觉是那么回事，稀里糊涂的先把题目过了。
这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。 这么一说好像很简单！
都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。
那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？
回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）
强调一下，树层去重的话，需要对数组排序！
选择过程树形结构如图所示：
回溯三部曲
此题需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。
这个集合去重的重任就是used来完成的。
代码如下：
1
2
3
| vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
|
终止条件为 sum > target 和 sum == target。
代码如下：
1
2
3
4
5
6
7
| if (sum > target) {
return;
}
if (sum == target) {
result.push_back(path);
return;
}
|
sum > target 这个条件其实可以省略，因为在递归单层遍历的时候，会有剪枝的操作，下面会介绍到。
前面我们提到：要去重的是“同一树层上的使用过”，如何判断同一树层上元素（相同的元素）是否使用过了呢。
**如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]**。
此时for循环里就应该做continue的操作。
这块比较抽象，如图：
在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：
- used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
- used[i - 1] == false，说明同一树层candidates[i - 1]使用过
可能有的录友想，为什么 used[i - 1] == false 就是同一树层呢，因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。
而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上，如图所示：
这块去重的逻辑很抽象，网上搜的题解基本没有能讲清楚的，如果大家之前思考过这个问题或者刷过这道题目，看到这里一定会感觉通透了很多！
那么单层搜索的逻辑代码如下：
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
| for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
used[i] = true;
backtracking(candidates, target, sum, i + 1, used);
used[i] = false;
sum -= candidates[i];
path.pop_back();
}
```
**注意sum + candidates\[i] <= target为剪枝操作**
- 时间复杂度: O(n * 2^n)
- 空间复杂度: O(n)
### 补充
这里直接用startIndex来去重也是可以的， 就不用used数组了。
```c++
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
if (i > startIndex && candidates[i] == candidates[i - 1]) {
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i + 1);
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
path.clear();
result.clear();
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0);
return result;
}
};
|
代码实现
使用标记数组
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
| class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
boolean[] used;
int sum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
used = new boolean[candidates.length];
Arrays.fill(used, false);
Arrays.sort(candidates);
backTracking(candidates, target, 0);
return ans;
}
private void backTracking(int[] candidates, int target, int startIndex) {
if (sum == target) {
ans.add(new ArrayList(path));
}
for (int i = startIndex; i < candidates.length; i++) {
if (sum + candidates[i] > target) {
break;
}
if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;
sum += candidates[i];
path.add(candidates[i]);
backTracking(candidates, target, i + 1);
used[i] = false;
sum -= candidates[i];
path.removeLast();
}
}
}
|
不使用标记数组
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
| class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
int sum = 0;
public List<List<Integer>> combinationSum2( int[] candidates, int target ) {
Arrays.sort( candidates );
backTracking( candidates, target, 0 );
return res;
}
private void backTracking( int[] candidates, int target, int start ) {
if ( sum == target ) {
res.add( new ArrayList<>( path ) );
return;
}
for ( int i = start; i < candidates.length && sum + candidates[i] <= target; i++ ) {
if ( i > start && candidates[i] == candidates[i - 1] ) {
continue;
}
sum += candidates[i];
path.add( candidates[i] );
backTracking( candidates, target, i + 1 );
int temp = path.getLast();
sum -= temp;
path.removeLast();
}
}
}
|
131.分割回文串※
建议：本题较难，大家先看视频来理解 分割问题，明天还会有一道分割问题，先打打基础。
题目链接： https://leetcode.cn/problems/palindrome-partitioning/
文章讲解： https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html
视频讲解： https://www.bilibili.com/video/BV1c54y1e7k6
题目分析
方案一
依靠自己的摸索，使得本题正常AC，十分惊喜，虽然耗费了较长的时间
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
| class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backtracking(s, 0, new ArrayList<>(), result);
return result;
}
private void backtracking(String s, int start, List<String> temp, List<List<String>> result) {
if (start == s.length()) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = start; i < s.length(); i++) {
String substring = s.substring(start, i + 1);
if (!isPalindromic(substring)) continue;
temp.add(substring);
backtracking(s, i + 1, temp, result);
temp.remove(temp.size() - 1);
}
}
private boolean isPalindromic(String s) {
int start = 0, end = s.length() - 1;
while (start < end) {
if (s.charAt(start++) != s.charAt(end--)) return false;
}
return true;
}
}
|
结果
解答成功:
执行耗时:6 ms,击败了98.84% 的Java用户
内存消耗:54.3 MB,击败了33.57% 的Java用户
分析
时间复杂度：
O( n * 2^n )
空间复杂度：
O( n^2 )
代码随想录
https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html
思路
本题这涉及到两个关键问题：
- 切割问题，有不同的切割方式
- 判断回文
相信这里不同的切割方式可以搞懵很多同学了。
这种题目，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯。
回溯究竟是如何切割字符串呢？
来分析一下切割，其实切割问题类似组合问题。
例如对于字符串abcdef：
- 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…..。
- 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…..。
所以切割问题，也可以抽象为一棵树形结构，如图：
递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
回溯三部曲
全局变量数组path存放切割后回文的子串，二维数组result存放结果集。 （这两个参数可以放到函数参数里）
本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。
代码如下：
1
2
3
| vector<vector<string>> result;
vector<string> path;
void backtracking (const string& s, int startIndex) {
|
从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。
那么在代码里什么是切割线呢？
在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。
所以终止条件代码如下：
1
2
3
4
5
6
7
| void backtracking (const string& s, int startIndex) {
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
}
|
来看看在递归循环中如何截取子串呢？
在for (int i = startIndex; i < s.size(); i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文，如果是回文，就加入在vector<string> path中，path用来记录切割过的回文子串。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
| for (int i = startIndex; i < s.size(); i++) {
if (isPalindrome(s, startIndex, i)) {
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
} else {
continue;
}
backtracking(s, i + 1);
path.pop_back();
}
|
注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1。
判断回文子串
最后我们看一下回文子串要如何判断了，判断一个字符串是否是回文。
可以使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串了。
那么判断回文的C++代码如下：
1
2
3
4
5
6
7
8
| bool isPalindrome(const string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
|
如果大家对双指针法有生疏了，传送门：双指针法：总结篇！(opens new window)
此时关键代码已经讲解完毕，整体代码如下（详细注释了）
根据Carl给出的回溯算法模板：
1
2
3
4
5
6
7
8
9
10
11
12
13
| void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表);
回溯，撤销处理结果
}
}
|
不难写出如下代码：
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
| class Solution {
private:
vector<vector<string>> result;
vector<string> path;
void backtracking (const string& s, int startIndex) {
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
for (int i = startIndex; i < s.size(); i++) {
if (isPalindrome(s, startIndex, i)) {
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
} else {
continue;
}
backtracking(s, i + 1);
path.pop_back();
}
}
bool isPalindrome(const string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
};
|
- 时间复杂度: O(n * 2^n)
- 空间复杂度: O(n^2)
优化
上面的代码还存在一定的优化空间, 在于如何更高效的计算一个子字符串是否是回文字串。上述代码isPalindrome函数运用双指针的方法来判定对于一个字符串s, 给定起始下标和终止下标, 截取出的子字符串是否是回文字串。但是其中有一定的重复计算存在:
例如给定字符串"abcde", 在已知"bcd"不是回文字串时, 不再需要去双指针操作"abcde"而可以直接判定它一定不是回文字串。
具体来说, 给定一个字符串s, 长度为n, 它成为回文字串的充分必要条件是s[0] == s[n-1]且s[1:n-1]是回文字串。
大家如果熟悉动态规划这种算法的话, 我们可以高效地事先一次性计算出, 针对一个字符串s, 它的任何子串是否是回文字串, 然后在我们的回溯函数中直接查询即可, 省去了双指针移动判定这一步骤.
具体参考代码如下:
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
| class Solution {
private:
vector<vector<string>> result;
vector<string> path;
vector<vector<bool>> isPalindrome;
void backtracking (const string& s, int startIndex) {
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
for (int i = startIndex; i < s.size(); i++) {
if (isPalindrome[startIndex][i]) {
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
} else {
continue;
}
backtracking(s, i + 1);
path.pop_back();
}
}
void computePalindrome(const string& s) {
isPalindrome.resize(s.size(), vector<bool>(s.size(), false));
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = i; j < s.size(); j++) {
if (j == i) {isPalindrome[i][j] = true;}
else if (j - i == 1) {isPalindrome[i][j] = (s[i] == s[j]);}
else {isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i+1][j-1]);}
}
}
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
computePalindrome(s);
backtracking(s, 0);
return result;
}
};
|
难点：
- 切割问题可以抽象为组合问题
- 如何模拟那些切割线
- 切割问题中递归如何终止
- 在递归循环中如何截取子串
- 如何判断回文
平时在做难题的时候，总结出来难究竟难在哪里也是一种需要锻炼的能力。
可能遇到题目比较难，但是不知道题目难在哪里，反正就是很难。其实这样还是思维不够清晰，这种总结的能力需要多接触多锻炼。
本题第一个难点上：就是不知道如何切割，甚至知道要用回溯法，也不知道如何用。也就是没有体会到按照求组合问题的套路就可以解决切割。
如果意识到这一点，算是重大突破了。接下来就可以对着模板照葫芦画瓢。
但接下来如何模拟切割线，如何终止，如何截取子串，其实都不好想，最后判断回文算是最简单的了。
关于模拟切割线，其实就是index是上一层已经确定了的分割线，i是这一层试图寻找的新分割线
除了这些难点，本题还有细节，例如：切割过的地方不能重复切割所以递归函数需要传入i + 1。
所以本题应该是一道hard题目了。
代码实现
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
| class Solution {
List<List<String>> lists = new ArrayList<>();
Deque<String> deque = new LinkedList<>();
public List<List<String>> partition(String s) {
backTracking(s, 0);
return lists;
}
private void backTracking(String s, int startIndex) {
if (startIndex >= s.length()) {
lists.add(new ArrayList(deque));
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isPalindrome(s, startIndex, i)) {
String str = s.substring(startIndex, i + 1);
deque.addLast(str);
} else {
continue;
}
backTracking(s, i + 1);
deque.removeLast();
}
}
private boolean isPalindrome(String s, int startIndex, int end) {
for (int i = startIndex, j = end; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
}
|