Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-07

ShortPalindromes

| 12:58

問題文

与えられた文字列から作られる、最も短くて、辞書順で最初にくる回文を作れ、という問題。再帰+メモ化によって時間内に解ける問題。わからなくてEditorialを見た。思いつきそうでつかない解法だな。こういう問題は慣れれば解けるようになると思った。

572.72/1150 - 00:38:45 (cheated)

class ShortPalindromes {
    public:
        string shortest(string base) {
            memo.clear();
            return go(base);
        }
    private:
        map<string,string> memo;
        string go(const string& s) {
            if (memo.find(s) != memo.end()) 
                return memo[s];
            if (isPalindrome(s)) 
                return s;
            const int len = s.length();
            string ret;
            if (s[0] == s[len-1]) {
                ret = string(1,s[0]) + go(s.substr(1,len-2)) + string(1,s[0]);
            } else {
                ret = minStr(string(1,s[0]) + go(s.substr(1,len-1)) + string(1,s[0]),
                        string(1,s[len-1]) + go(s.substr(0,len-1)) + string(1,s[len-1]));
            }
            memo[s] = ret;
            return ret;
        }
        bool isPalindrome(const string& s) {
            const int len = s.length();
            for (int i = 0; i < len/2; i++)
                if (s[i] != s[len-i-1])
                    return false;
            return true;
        }
        string minStr(const string& a, const string& b) {
            if (a.length() < b.length()) {
                return a;
            } else if (a.length() > b.length()) {
                return b;
            } else if (a < b) {
                return a;
            } else {
                return b;
            }
        }
};