Q(2) Given a string of characters without any spaces between them and a dictiona
ID: 3698710 • Letter: Q
Question
Q(2) Given a string of characters without any spaces between them and a dictionary of valid English words, find all possible ways to break the string in individual dictionary words. Examples: dictionary ["T", "have", "Sam", "am", "this", "dog"] String "lamSam" Outpt: "I am Sam" String thisisadog" Output:String can't be broken a) Design the recursive sub-problem condition(s) b) Use your solution in (a) to solve the following problems: You have to show the complete solution of the DP steps either by top down or bottom-up approach. dictionary-["I" , "KU", "study", "???", "in"] string input: "IstudyCpEinkU 2nd string input: "IstudyEEinKU c What is the running time of your algorithm? Note: your solution must not run in exponential timeExplanation / Answer
Here is the correction hope this helps:
import java.util.HashSet;
public class WordBreak {
public boolean findUsingDP(String s, HashSet<String> dict,
HashSet<String> memory, String answer) {
if (s.length() == 0) {
System.out.println(answer);
return true;
} else if (memory.contains(s)) {
return false;
} else {
int index = 0;
String word = "";
while (index < s.length()) {
word += s.charAt(index);// add one char at a time
// check if word already being solved
if (dict.contains(word)) {
if (findUsingDP(s.substring(index + 1), dict, memory,
answer + word + " ")) {
return true;
} else {
System.out.println("backtrack");
index++;
}
} else {
index++;
}
}
memory.add(s);// memoization for future;
return false;
}
}
public static void main(String[] args) {
HashSet<String> hs = new HashSet<String>();
hs.add("I");
hs.add("KU");
hs.add("study");
hs.add("CpE");
hs.add("in");
String s = "IstudyCpEinKU";
WordBreak ws = new WordBreak();
// create another HashSet so store the sub problems result
HashSet<String> memoization = new HashSet<String>();
ws.findUsingDP(s, hs, memoization, "");
}
c)Running time of this algorithm is:
Since we are calculating result[N] back to result[0], and each of these calculations take O(N) (because subproblems we depend on have been calculated), the time complexity should be O(N^2).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.