Undo format when format disappears

Question

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));  
        }
    }
}

Answer 1

public class UndoFormat {

As already said, this is a terrible name. It sort of undoes something, but this something is definitely no formatting. DictionarySplitter or WordSplitter would do.

// Container class to hold the total number of
// character misses for the list of string.

This should be Javadoc.

class Pair {

It is a pair, but there should be a better name. I'd also make the class private. Actually, I'd always make everything as private as possible.

    private int miss;
    int getMissedChars() {

So, miss or missedChars? The names should correspond with each other. It's the "number of misses" or "missed count", so I'd go for misses (according to the old Sun's conventions it should be nMisses, but I can't recall seeing it anywhere).

    List<String> getStrings() {

By returning a List, you allow anyone to indirectly modify your Pair. That's fine for a (package) private method, just be aware of it.

// Cache to store the intermediate computations
private Map<String, Pair> cache = new HashMap<String, Pair>();

The comment does not help. As all you're doing is computation, there's nothing else to be stored. I'd leave it out.

    // Seeding the dictionary for testing purposes
    dict.add("is");

Seeding the dictionary for testing purposes is fine, but surely shouldn't be done in the constructor. Keep such things as external as possible, i.e., move it to main or to a test class. Otherwise

• It gets always invoked.
• You don't see if the class is really usable from the outside.

---

public Pair undoFormat(String str) {

As already said, split would be a better name. Actually, with caching, I always tend to write two methods: uncachedSplit (private method doing the real work) and split (public method adding the caching). This clearly separates the responsibilities and makes early returns simpler (and you'll never forget to cache the new result).

    // If the cache contains the string,its cost has already been computed return it

I'd drop it. It's correct, but obvious.

        return pair;
    } else {

After "return", "else" gets rarely used (it may be useful for preserving symmetry or in a "else-if" chain). By dropping it, you can unindent most of your code.

        int currentMiss = targetString.length();
        List<String> currentList = Arrays.asList(targetString);

Synchronize these names with the Pair member names. Or better, create a Pair instead.

        for (int i = 1; i < str.length(); i++) {

This allows a zero lengt for the second substring, but not for the first. Why?

            String firstHalf = str.substring(0, i);
            String nextHalf = str.substring(i, str.length());

Your meaning of "half" is rather wide, I'd use "part". Speaking of "next" in the sense of "second" is not optimal either. I'd go either for part1 and part2 or head and tail.

Passing str.length() above is superfluous.

            Pair fPair = undoFormat(firstHalf);
            Pair nPair = undoFormat(nextHalf);

I really dislike these names. If you used fHalf and nHalf above, it'd be better (ugly, but consistent).

You're creating tons of single-use local variables here. That's surely better than overlong expressions, but the sweet spot lies somewhere in the middle. Actually, your Pair is a pure data container and could use methods like

Pair combine(Pair other);
Pair better(Pair other);

which would make the loop body to

for (int i = 1; i < str.length() - 1; i++) {
    Pair first = split(str.substring(0, i));
    Pair second = split(str.substring(i));
    Pair current = first.combine(second);
    result = result.better(current);
}

You can see I left out "pair" from the names as I needed nothing but pairs.

All in all, it's fine and easy to understand. My main concern is the naming. With more consequent naming and some helper methods, you'll use hardly any comments as everything gets perfectly clear.

Answer 2

The output is not as expected:

The formatted string is:S
The formatted string is:a
The formatted string is:M
The formatted string is:is
The formatted string is:a
The formatted string is:bad
The formatted string is:man

While it should be:

The formatted string is:SAM
The formatted string is:is
The formatted string is:a
The formatted string is:bad
The formatted string is:man

I'd rename the class to DictionarySplitter and undoFormat() to split().