TopCoder SRM 149 DIV 1 Medium 練習

問題

単語一覧が与えられるので、与えられた文字列の適切な位置にスペースを挟んで、もとの単語の並びを復元しなさい。ただし複数の解が存在するなら AMBIGUOUS! を、解が存在しないなら IMPOSSIBLE! を返しなさい。

解

最初に必殺総当り再帰で解いて、時間オーバー。

メモ化すればいいじゃん、って思い立つのに30分ぐらいかかった。鬱だ。

あと少し迷ったのは、一回でもAMBIGUOUSが出たら、確実に返すべき値は AMBIGUOUS! になるんだけど、それを伝播させなきゃいけないってことかな。コメントでマークしてあるとこ。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class MessageMess {
    string[] dict;
    public string restore(string[] dictionary, string message)
    {
        dict = dictionary;
        return srch(message);
    }

    Dictionary<string, string> memo = new Dictionary<string, string>();
    private string srch(string message)
    {
        if (message == "") return "";
        if (memo.ContainsKey(message)) return memo[message];
        string res = "", tmp = "";
        int sols = 0;
        for (int i = 0; i < message.Length; ++i)
        {
            tmp += message[i];
            if (Array.IndexOf(dict, tmp) != -1)
            {
                string p = srch(message.Substring(i + 1));
                if (p == "IMPOSSIBLE!") continue;
                if (p == "AMBIGUOUS!")
                {
                    res = "AMBIGUOUS!";    // AMBIGUOUSは繋がっていくのだよ
                    break;
                }

                sols++;
                res = tmp + (p != "" ? " " : "") + p;
            }
        }
        if (sols >= 2) res = "AMBIGUOUS!";
        else if (res == "") res = "IMPOSSIBLE!";
        return memo[message] = res;
    }
}