131. 分割回文串

叁歲伎倆 2024-03-30 12:17 60阅读 0赞

### 131. 分割回文串 ###

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 **回文串** 。返回 s 所有可能的分割方案。

**回文串** 是正着读和反着读都一样的字符串。

##### 示例 1： #####

> 输入：s = “aab”  
> 输出：\[\[“a”,“a”,“b”\],\[“aa”,“b”\]\]

##### 示例 2： #####

> 输入：s = “a”  
> 输出：\[\[“a”\]\]

##### 提示： #####

1 <= s.length <= 16  
s 仅由小写英文字母组成

#### 思路：(回溯) ####

*  回溯万能模板：[46. 全排列][46.]
 *  同样可以使用回溯求解的题目：[40. 组合总和 II][40. _ II]

**本题解题关键：对字符串的处理**

1.  把所有字符串看成：前缀字符串 + 剩余字符串
2.  如果前缀字符串是回文， 则将剩余字符串当作新的字符串，进行递归再次分割
3.  如果前缀字符串不是回文，则前缀长度+1，重复以上操作。

其树形结构为：  
![在这里插入图片描述][fc272d18ee41430083799ad348310b08.png]

#### 代码(Java) ####

import java.util.ArrayList;
    import java.util.List;
    
    public class splitString {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		String s = "aab";
    		System.out.println(partition(s));
    	}
    	public static List<List<String>> partition(String s) {
        
    		List<List<String>> combinations = new ArrayList<>();
    		List<String> combination = new ArrayList<>();
    		backtracking(combinations, combination, s);
    		return combinations;
    	}
    	private static void backtracking(List<List<String>> combinations, List<String> combination, String s) {
        
    		// TODO Auto-generated method stub
    		if(s.length() == 0) {
        
    			combinations.add(new ArrayList<>(combination));
    			return;
    		}
    		for(int i = 1; i <= s.length(); i++) {
        
    			if(isPalindrome(s.substring(0, i))) {
        
    				combination.add(s.substring(0,i));
    				backtracking(combinations, combination, s.substring(i));
    				combination.remove(combination.size() - 1);
    			}
    		}
    		
    	}
    	private static boolean isPalindrome(String s) {
        
    		int n = s.length();
    		int i = 0;
    		while( i != n / 2) {
        
    			if(s.charAt(i) != s.charAt(n - 1 - i))
    				return false;
    			i++;
    		}
    		return true;
    	}
    }

##### 运行结果： #####

![在这里插入图片描述][66301c517ff54322a403ab3c22e70380.png]

##### 注：仅供学习参考！ #####

题目来源：[力扣.][.]

[46.]: https://blog.csdn.net/weixin_43412762/article/details/128160319?spm=1001.2014.3001.5501
[40. _ II]: https://blog.csdn.net/weixin_43412762/article/details/128430757?spm=1001.2014.3001.5501
[fc272d18ee41430083799ad348310b08.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/95959e5b4d79469bbcfe6e0c1e6988e1.png
[66301c517ff54322a403ab3c22e70380.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7ad7feff0ec64f11843b0f581bb383e7.png
[.]: https://leetcode.cn/problems/palindrome-partitioning/description/