fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main(String[] args) throws java.lang.exception{
  11. 		System.out.println(minCuts("ABCD"));
  12. 	}
  13.  
  14. 	static HashMap<Integer, HashSet<Integer>> palindromes = new HashMap<>();
  15.  
  16. 	public static int minCuts(String str) {
  17. 		int[] arr = new int[str.length() + 1];
  18. 		Arrays.fill(arr, Integer.MAX_VALUE);
  19. 		arr[str.length()] = -1;
  20. 		fillPalindromes(str);
  21. 		for (int i = str.length() - 1; i >= 0; i--)
  22. 			for (int j = i; j < str.length(); j++) {
  23. 				if (palindromes.containsKey(i))
  24. 					if (palindromes.get(i).contains(j))
  25. 						arr[i] = arr[i] > arr[j + 1] + 1 ? arr[j + 1] + 1 : arr[i];
  26. 			}
  27. 		return arr[0];
  28. 	}
  29.  
  30. 	public static void fillPalindromes(String str) {
  31. 		for (int i = 0; i < str.length(); i++) {
  32. 			for (int j = 0; i - j >= 0 && j + i < str.length(); j++)
  33. 				if (str.charAt(i - j) == str.charAt(j + i)) {
  34. 					if (palindromes.containsKey(i - j))
  35. 						palindromes.get(i - j).add(i + j);
  36. 					else {
  37. 						HashSet<Integer> hs = new HashSet<>();
  38. 						hs.add(i + j);
  39. 						palindromes.put(i - j, hs);
  40. 					}
  41. 				} else
  42. 					break;
  43. 		}
  44. 		for (double i = 0.5; i < str.length() - 1; i++)
  45. 			for (double j = 0.5; i - j >= 0 && i + j < str.length(); j++)
  46. 				if (str.charAt((int) (i - j)) == str.charAt((int) (i + j))) {
  47. 					if (palindromes.containsKey((int) (i - j)))
  48. 						palindromes.get((int) (i - j)).add((int) (i + j));
  49. 					else {
  50. 						HashSet<Integer> hs = new HashSet<>();
  51. 						hs.add((int) (i + j));
  52. 						palindromes.put((int) (i - j), hs);
  53. 					}
  54.  
  55. 				} else
  56. 					break;
  57. 	}
  58. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:10: error: cannot find symbol
	public static void main(String[] args) throws java.lang.exception{
	                                                       ^
  symbol:   class exception
  location: package java.lang
1 error
stdout
copy 
Standard output is empty
https://ideone.com/qj1uDm
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!