rocketegg
BAN USER@Miguel - the O(string_len) only holds because the language is defined here as containing "hire". If it contained more characters, w/o dynamic programming you're looking at O(n^2).
@Nothing Special - I agree with your set comment. As for the second, with dynamic programming it's true that every permutation of the string has to be computed the first time, but subsequent calls are all cached so would be much faster.
If you assume that the sentence is valid (i.e. has all valid words), then the difficulty is that you have to check whether trying a subword breaks the validity of the rest of the sentence. So what you can do is traverse through the string, whenever you find a word, push a pointer to a stack and restart the counter to track the current word. If you end up getting to the end of the "sentence" and your current word is not a word, then you know the subword was wrong, so pop the stack and try a longer word. See this implementation below:
public static String reconstructSentence(String s, HashMap<String, Boolean> dictionary) {
int ptr = 0;
Stack<Integer> spaces = new Stack<Integer>();
spaces.add(ptr);
String currWord = "";
while (!spaces.isEmpty()) {
currWord = s.substring(spaces.peek(), ptr);
System.out.println("Curr Word: " + currWord);
if (dictionary.containsKey(currWord)) {
System.out.println(">>>Found word: " + currWord);
spaces.push(ptr);
}
if (ptr >= s.length()) { //reached the end
if (dictionary.containsKey(currWord)) {
System.out.println("Sentence is done!");
spaces.push(ptr); //Done.
break;
}
System.out.println("Backtracking ...");
if (spaces.isEmpty()) {
System.out.println("Sentence could not be reconstructed");
break;
} else {
ptr = spaces.pop();
}
}
ptr++;
}
//Reconstruct Sentence
int to = s.length();
String sentence = "";
while (!spaces.isEmpty()) {
int from = spaces.pop();
String word = s.substring(from, to);
to = from;
sentence = word + " " + sentence;
}
return sentence;
}
//Try it with this unit test.
public void testValidSentence() {
HashMap<String, Boolean> dictionary = new HashMap<String, Boolean>();
dictionary.put("the", true);
dictionary.put("dog", true);
dictionary.put("went", true);
dictionary.put("to", true);
dictionary.put("park", true);
dictionary.put("in", true);
dictionary.put("sunshine", true);
dictionary.put("happy", true);
dictionary.put("do", true);
dictionary.put("sun", true);
dictionary.put("shine", true);
dictionary.put("sunny", true);
dictionary.put("on", true);
dictionary.put("a", true);
dictionary.put("day", true);
String sentence = "thehappydogwenttotheparkonasunnyday";
System.out.println(sentence + " Reconstructed: " + StringUtil.reconstructSentence(sentence, dictionary));
}
Output: thehappydogwenttotheparkonasunnyday Reconstructed: the happy dog went to the park on a sunny day
- rocketegg October 23, 2013How about a recursive dynamic programming approach? For a word to conform to a language, all sub-words must also conform to the language. You can cut down on calls by calling isValidWord on substring from 1 - s.length()-1, but you dictionary won't fill as fast.
private static HashMap<String, Boolean> dictionary = new HashMap<String, Boolean>();
/**
* Returns whether a word is a valid "word", i.e. made up of characters
* in the character array
* @param c
* @return
*/
public static boolean isValidWord(String s, char [] c) {
if (dictionary.containsKey(s)) { //word found in dictionary
return true;
}
if (s.length() == 0) //empty words are in the language
return true;
boolean goLeft = false;
boolean goRight = false;
for (int i = 0; i < c.length; i++) { //if word not in dictionary, check ends
if (s.charAt(0) == c[i])
goLeft = true;
if (s.charAt(s.length()-1) == c[i])
goRight = true;
}
if (s.length() <= 1 && goLeft && goRight)
return true;
if (goLeft == false || goRight == false) {
return false;
}
boolean isValid = isValidWord(s.substring(1, s.length()), c) && isValidWord(s.substring(0, s.length()-1), c);
if (isValid) {
dictionary.put(s.substring(1, s.length()-1), true);
}
return isValid;
}
The key insight here is that doing a binary search of a rotated array is that portions of the array are still sorted, or represent another rotated array to search in. Thus, if you have the array
[7, 8, 1, 2, 3, 4, 5, 6], and you are searching for '5', this can be found in the second half of the array. So you need to tell binary search when to look in the sorted half, vs when to look in the unsorted half.
Example: If your index in binary search is 3, your value is 2, so you know the right portion will be sorted. If 5 is between 2 and the last element (6), just do binary search. Otherwise, the target would have to be in the first half (or nowhere at all). See the code below.
- rocketegg November 05, 2013