131. Palindrome Partitioning.md

131. Palindrome Partitioning

---

leetcode Daily Challenge on December 14th, 2020.

leetcode-cn Daily Challenge on March 7th, 2021.

---

Difficulty : Medium

Related Topics : Dynamic Programming、Backtracking、DFS

---

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

• 1 <= s.length <= 16
• s contains only lowercase English letters.

---

Solution

• mine
  • Java
    • Runtime: 41 ms, faster than 5.03%, Memory Usage: 66.1 MB, less than 5.31% of Java online submissions

      public List<List<String>> partition(String s) {
          List<List<String>> res = new LinkedList<>();
          if(s == null || s.length() == 0) return res;
      
          char[] arr = s.toCharArray();
          for(int i = 1; i <= arr.length; i++){
              if(!check(arr, 0, i -1)){
                  continue;
              }
              String t = s.substring(0, i);
              List<List<String>> sub = partition(s.substring(i));
              if(sub.size() == 0){
                  List<String> list = new LinkedList<>();
                  list.add(t);
                  res.add(list);
              }else{
                  for(List<String> sublist : sub){
                      LinkedList<String> linkedList = new LinkedList<>(sublist);
                      linkedList.addFirst(t);
                      res.add(linkedList);
                  }
              }
          }
          return res;
      }
      
      boolean check(char[] arr, int l, int r){
          while(l < r){
              if(arr[l++] != arr[r--]) return false;
          }
          return true;
      }
      

---

• the most votes

• Runtime: 8 ms, faster than 17.28%, Memory Usage: 53 MB, less than 6.19% of Java online submissions

  List<List<String>> list = new ArrayList<>();
  public List<List<String>> partition(String s) {
      dfs(s, 0, new ArrayList<>());
      return list;
  }
  
  private void dfs(String s, int start, List<String> curL){
      if(start >= s.length()) list.add(new ArrayList<>(curL));
      for(int end = start; end < s.length(); end++){
          if(isPalindrome(s, start, end)){
              curL.add(s.substring(start, end + 1));
              dfs(s, end + 1, curL);
              curL.remove(curL.size() - 1);
          }
      }
  }
  
  private boolean isPalindrome(String s, int l, int r){
      while(l <= r){
          if(s.charAt(l) != s.charAt(r)) return false;
          l++;
          r--;
      }
      return true;
  }
  

---