Advertisement
yimengael

Palindromic Decomposition

May 17th, 2022
779
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2. import java.util.List;
  3. import java.util.ArrayList;
  4.  
  5. public class PalindromicDecomposition {
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         int t = sc.nextInt();
  9.         sc.nextLine();
  10.         while (t-- > 0) {
  11.             String s = sc.nextLine();
  12.             printNestedListOfString(palindromicPartitioning(s));
  13.         }
  14.     }
  15.  
  16.     public static List<List<String>> palindromicPartitioning(String input) {
  17.         List<List<String>> result = new ArrayList<>();
  18.         palindromicPartitioningHelper(input, 0, new ArrayList<String>(), result);
  19.         return result;
  20.     }
  21.  
  22.     public static void palindromicPartitioningHelper(String input, int idx, List<String> soFar, List<List<String>> result) {
  23.         if (idx == input.length()) {
  24.             result.add(new ArrayList<>(soFar));
  25.             return;
  26.         }
  27.  
  28.         for (int i = idx + 1; i <= input.length(); i++) {
  29.             String prefix = input.substring(idx, i);
  30.             if (isPalindrome(prefix)) {
  31.                 soFar.add(prefix);
  32.                 palindromicPartitioningHelper(input, i, soFar, result);
  33.                 soFar.remove(soFar.size() - 1);
  34.             }
  35.         }
  36.     }
  37.  
  38.     public static boolean isPalindrome(String s) {
  39.         for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
  40.             if (s.charAt(i) != s.charAt(j)) {
  41.                 return false;
  42.             }
  43.         }
  44.         return true;
  45.     }
  46.  
  47.     public static void printNestedListOfString(List<List<String>> outer) {
  48.         StringBuilder sb = new StringBuilder();
  49.         sb.append('[');
  50.         for (List<String> inner : outer) {
  51.             sb.append(inner.toString()).append(", ");
  52.         }
  53.         sb.deleteCharAt(sb.length() - 1);
  54.         sb.deleteCharAt(sb.length() - 1);
  55.         sb.append(']');
  56.         System.out.println(sb.toString());
  57.     }
  58. }
Advertisement
RAW Paste Data Copied
Advertisement