分割字符串使得每個部分都是回文數(shù)

131. Palindrome Partitioning (Medium)

For example, given s = "aab", Return[["aa","b"],["a","a","b"] ]

題目描述：

給定一個字符串，將其分割成回文串，并返回所有的分割結(jié)果。

思路分析：

求子串問題，也可以用到回溯思想，我們只需要判斷分割出來的字符串是否是回文，如果是回文就添加到結(jié)果中。

代碼：

public List<List<String>>partition(String s){List<List<String>>res=new ArrayList<>();List<String>list=new ArrayList<>();doPartition(s,res,list);return res; } public void doPartition(String s,List<List<String>>res,List<String>list){if(s.length()==0){res.add(new ArrayList<>(list));return;}for(int i=0;i<s.length();i++){if(isPalindrome(s,0,i)){ //判斷是否為回文list.add(s.substring(0,i+1));doPartition(s.substring(i+1),res,list);list.remove(list.size()-1);}} } public boolean isPalindrome(String s,int start,int end){while(start<end){if(s.charAt(start++)!=s.charAt(end--))return false;}return true; }

轉(zhuǎn)載于:https://www.cnblogs.com/yjxyy/p/11114261.html

總結(jié)

以上是生活随笔為你收集整理的回溯---分割字符串使得每个部分都是回文数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。