首页 > 代码库 > [leetcode]Palindrome Partitioning

[leetcode]Palindrome Partitioning

2024-07-12 05:58:22   223人阅读

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
 1 public class Solution { 2     List<List<String>> result = new ArrayList<List<String>>(); 3      4     public List<List<String>> partition(String s) { 5         if(s == null || s.length() == 0) return result; 6         dfs(new ArrayList<String>(),s); 7         return result; 8     } 9     private void dfs(List<String> list,String s){10         if(s.length() == 0){11             result.add(new ArrayList<String>(list));12             return;13         }14         for(int i = 0; i < s.length(); i++){15             String pre = s.substring(0, i + 1);16             if(isPalindrome(pre)){17                 list.add(pre);18                 dfs(list, s.substring(i + 1));19                 list.remove(list.size() - 1);20             }21         }22     }23     private boolean isPalindrome(String s){24         for(int i = 0; i <= s.length() / 2; i++){25             if(s.charAt(i) != s.charAt(s.length() - 1 - i)) return false;26         }27         return true;28     }29 }

jd的做法几乎一样，并在博文下面借鉴了两篇其他博文，其中有个DP算法可以看一下。

 


联系
我们