Alternativ lösning 3: Index i yttre loop, tokens i inre

2011-02-18 — Tobias HillTobias Hill

En av våra interna referenslösningar på Citerus skrevs av Patrik Åkerfeldt och hade ett löpande index i den yttre loopen och tokens-iteration i den inre. Som optimering hoppar den över redan genomsökta delar av strängen i djupare rekursioner. 

public class PaakReducer {

    public int stepBackAtMatch = 0;

    private int shortestStringLength = Integer.MAX_VALUE;
    private String shortest;
    private String[] reducers;

    public PaakReducer(String... reducers) {
        this.reducers = reducers;
        int maxLen = 0;
        for (String reducer : reducers) {
            maxLen = Math.max(reducer.length(), maxLen);
        }
        stepBackAtMatch = maxLen - 1;
    }

    public String reduce(String target) {
        recursive(target, 0);
        return shortest;
    }

    private void recursive(String target, int startIndex) {
        int index = (startIndex < 0 ? 0 : startIndex);

        while (index < target.length()) {
            for (String r : reducers) {
                if (target.substring(index).startsWith(r)) {
                    String newtarget = target.substring(0, index) + target.substring(index + r.length());
                    recursive(newtarget, index - stepBackAtMatch);
                }
            }
            index++;
        }

        if (target.length() < shortestStringLength) {
            shortestStringLength = target.length();
            shortest = target;
        }
    }
}