TopCoder SRM579: UndoHistory

各行ごとに buffer を使う場合と、undo を使う場合を試して、手数が少ない方を採用する。

public class UndoHistory {
    int CommonPrefixLength(string a, string b) {
        return a.Zip(b, (c1, c2) => c1 == c2).TakeWhile(v => v).Count();
    }

    public int minPresses(string[] lines) {
        string buffer = "";
        List<String> history = new List<string>();
        history.Add(buffer);
        int ans = 0;
        foreach (var line in lines) {
            int maxPrefix = history.Select(h => CommonPrefixLength(line, h)).Max();
            int typingWithUndo = 0, typingWithoutUndo = int.MaxValue;
            if (line.StartsWith(buffer)) {
                typingWithoutUndo = line.Length - buffer.Length + 1;
            }
            typingWithUndo += 2; // UNDO
            typingWithUndo += line.Length - maxPrefix; // TYPING
            typingWithUndo++; // ENTER
            history.Add(line);
            buffer = line;
            ans += Math.Min(typingWithoutUndo, typingWithUndo);
        }
        return ans;
    }
}