DP Code Given Above Has Some Issue I Fixed It: st…
PaNThErA - Dec 0, 2015
DP Code Given Above Has Some Issue I Fixed It:
static boolean wordBreak(String str, Set tokenMap) {
int size = str.length();
if (size == 0) return true;
// Create the DP table to store results of subroblems. The value wb[i]
// will be true if str[0..i-1] can be segmented into dictionary words,
// otherwise false.
boolean wb[] = new boolean[size + 1]; // default values are set to false
for (int i = 1; i <= size; i++) {
// if wb[i] is false, then check if current prefix can make it true.
// Current prefix is “str.substr(0, i)”
if (wb[i] == false && tokenMap.contains(str.substring(0, i)))
wb[i] = true;
// wb[i] is true, then check for all subStrings starting from
// (i+1)th character and store their results.
if (wb[i] == true) {
// If we reached the last prefix
if (i == size)
return true;
for (int j = i ; j <=size; j++) {
// Update wb[j] if it is false and can be updated
// Note the parameter passed to tokenMap.contains() is
// subString starting from index ‘i’ and length ‘j-i’
System.out.println(i+” “+j);
if (wb[j] == false && tokenMap.contains(str.substring(i, j)))
wb[j] = true;
// If we reached the last character
if (j == size && wb[j] == true)
return true;
}
}
}
/* Uncomment these lines to print DP table “wb[]”
for (int i = 1; i <= size; i++)
out.print(wb[i]+” “) */
// If we have tried all prefixes and none of them worked
return false;
}
Thanks PaNThEra, I got that my code had issues. Thank you so much for your working code. (Sorry for the delayed response)