fork download 
  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.  
  11. 	public static void main (String[] args) throws java.lang.Exception
  12. 	{
  13. 		String str = "ilikesamsung";
  14. 		HashSet<String> dictionary = new HashSet<String>(){{
  15.     add("i");
  16.     add("like");
  17.     add("likes");
  18.     add("samsung");
  19. }};
  20. 		wordBreak(str,dictionary);
  21. 	}
  22. static boolean wordBreak(String str, Set tokenMap) {
  23. int size = str.length();
  24. if (size == 0) return true;
  25.  
  26. // Create the DP table to store results of subroblems. The value wb[i]
  27. // will be true if str[0..i-1] can be segmented into dictionary words,
  28. // otherwise false.
  29. boolean wb[] = new boolean[size + 1]; // default values are set to false
  30.  
  31.  
  32. for (int i = 1; i <= size; i++) {
  33. // if wb[i] is false, then check if current prefix can make it true.
  34. // Current prefix is "str.substr(0, i)"
  35. if (wb[i] == false && tokenMap.contains(str.substring(0, i)))
  36. wb[i] = true;
  37.  
  38. // wb[i] is true, then check for all subStrings starting from
  39. // (i+1)th character and store their results.
  40. if (wb[i] == true) {
  41. // If we reached the last prefix
  42. if (i == size)
  43. return true;
  44. for (int j = i ; j <=size; j++) {
  45. // Update wb[j] if it is false and can be updated
  46. // Note the parameter passed to tokenMap.contains() is
  47. // subString starting from index 'i' and length 'j-i'
  48. System.out.println(i+" "+j);
  49. if (wb[j] == false && tokenMap.contains(str.substring(i, j)))
  50. wb[j] = true;
  51.  
  52. // If we reached the last character
  53. if (j == size && wb[j] == true)
  54. return true;
  55. }
  56. }
  57. }
  58.  
  59. /* Uncomment these lines to print DP table "wb[]"
  60. for (int i = 1; i <= size; i++)
  61. out.print(wb[i]+" ") */
  62.  
  63. // If we have tried all prefixes and none of them worked
  64. return false;
  65. }
  66. }
Success #stdin #stdout 0.12s 320576KB
comments (?)
stdin 
Standard input is empty
stdout 
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
5 5
5 6
5 7
5 8
5 9
5 10
5 11
5 12
https://ideone.com/gf2Q8Q
language:
Java (HotSpot 12)
created:
8 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!