首页 > 代码库 > Palindrome Partitioning

Palindrome Partitioning

2024-08-09 18:36:43   218人阅读

Palindrome Partitioning 

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [    ["aa","b"],    ["a","a","b"]  ]
参考了这个锅锅的，思路很清晰，用的类似DFS递归实现http://www.sjsjw.com/kf_code/article/033776ABA018056.asp


 1 import java.util.ArrayList; 2 import java.util.List; 3  4 public class Solution { 5      6     public List<List<String>> partition(String s) { 7         List<List<String>> result = new ArrayList<List<String>>();            //存放结果 8         List<String> curList = new ArrayList<String>();                        //记录当前结果 9         10         if(s.length() == 0)11             return result;12         getResult(result, curList, s);13         14         return result;15     }16     17     /**18      * 判断字符串是否为回文19      * @param str20      * @return21      */22     public boolean isPalindrom(String str){23         for(int i = 0, j = str.length() - 1; i < j; i++, j--){24             if(str.charAt(i) != str.charAt(j))25                 return false;26         }27         28         return true;29     }30     31     /**32      * 递归调用33      * @param curList34      * @param str35      */36     public void getResult(List<List<String>> result,List<String> curList, String str){37         if(str.length() == 0)38             result.add(new ArrayList<String>(curList));                //满足条件添加到结果集中,注意这里因为curList是引用，必须new一个新的list出来39         else{40             for(int i = 1; i <= str.length();i++){41                 String head = str.substring(0, i);42                 if(isPalindrom(head)){                                //子串是回文43                     curList.add(head);44                     getResult(result, curList, str.substring(i));45                     curList.remove(curList.size() - 1);46                 }47             }48         }49     }50 //    public void show(List<List<String>> list){51 //        for(List<String> list_temp : list){52 //            for(String string_temp : list_temp){53 //                System.out.print(string_temp + " ");54 //            }55 //            System.out.println();56 //        }57 //    }58 }

 

Palindrome Partitioning


联系
我们