I was posed a question as follows:
Given a sentence like "John is a bad man", lets say all the formatting disappears and you are left with one string "johnisabadman". Given a dictionary of words, design an algorithm to find the optimal way of "unconcatenating" the sequence of words. The optimality stems from the parsing which minimizes the number of unrecognized characters. In this particular example "johnisabadman" gets unconcatenated to "JOHN is a bad man".
I worked out a solution and it will be great if somebody could review it.
The algorithm works by checking if the original string is in the dictionary. If the dictionary contains the string, I return the string as it is, other wise I look at the substrings and recursively keep track of the cost of the substring in the inner class Pair
. The cost of the substring is zero if it is within the dictionary or else it is the length of the substring. While bubbling up from the recursion, I compare the sum of the cost of the substring with the original string and based on the comparison I decide whether to keep the concatenation of the substrings or the original string.
import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;
public class UndoFormat {
// Container class to hold the total number of
// character misses for the list of string.
class Pair {
private int miss;
private List<String> strings;
Pair(int miss, List<String> strings) {
this.miss = miss;
this.strings = strings;
}
int getMissedChars() {
return this.miss;
}
List<String> getStrings() {
return this.strings;
}
}
private Set<String> dict = new HashSet<String>();
// Cache to store the intermediate computations
private Map<String, Pair> cache = new HashMap<String, Pair>();
public UndoFormat() {
// Seeding the dictionary for testing purposes
dict.add("is");
dict.add("a");
dict.add("bad");
dict.add("man");
}
public Pair undoFormat(String str) {
// If the cache contains the string,its cost has already been computed return it
if (cache.containsKey(str)) {
return cache.get(str);
}
// If the dictionary contains the string, return the Pair with cost 0 and put the string and Pair in the cache
if (dict.contains(str)) {
Pair pair = new Pair(0, Arrays.asList(str));
cache.put(str, pair);
return pair;
} else {
// Dictionary doesn't contain the string, check the string
// against its substrings
String targetString = str.toUpperCase();
int currentMiss = targetString.length();
List<String> currentList = Arrays.asList(targetString);
List<String> currentMinList = currentList;
// If the Target string is 1-character long, return it
if (targetString.length() == 1) {
return new Pair(currentMiss, currentList);
}
// Recursively compare the cost of the substrings
for (int i = 1; i < str.length(); i++) {
String firstHalf = str.substring(0, i);
String nextHalf = str.substring(i, str.length());
Pair fPair = undoFormat(firstHalf);
Pair nPair = undoFormat(nextHalf);
int subMiss = fPair.getMissedChars() + nPair.getMissedChars();
List<String> combination = new ArrayList(fPair.getStrings());
combination.addAll(new ArrayList(nPair.getStrings()));
if (subMiss < currentMiss) {
currentMiss = subMiss;
currentMinList = combination;
} else if (subMiss == currentMiss) {
if (currentMinList.size() > combination.size()) {
currentMinList = combination;
}
}
}
Pair finalPair = new Pair(currentMiss, currentMinList);
cache.put(str, finalPair);
return finalPair;
}
}
public static void main(String[] args) {
UndoFormat uFormat = new UndoFormat();
List<String> formattedString = uFormat.undoFormat("johnisabadman").getStrings();
for (String fStr: formattedString) {
System.out.println(String.format("The formatted string is:%s", fStr));
}
}
}