记忆化搜索，类似邮局问题的dp。以下解法byACRush。
对于每一种string a -> string b，都有一个最小的转换步数。对长度分层考虑，当a首字符和b首字符相同时继续，当a首字符和b末字符相同时就可以调转。
class ReversalChain ...{
map < string, int > m; int minStep ( string a, string b )
...{ if ( a == b ) return 0; string hash = a + ' ' + b; int t = m[hash]; if ( t ) return t; int len = a.size (); t = 1 << 20; if ( a[0] == b[0] ) setMin ( t, minStep ( a.substr ( 1, len - 1 ), b.substr ( 1, len - 1 ) ) ); if ( a[len - 1] == b[len - 1] ) setMin ( t, minStep ( a.substr ( 0, len - 1 ), b.substr ( 0, len - 1 ) ) ); reverse ( a.begin (), a.end () ); if ( a[0] == b[0] ) setMin ( t, minStep ( a.substr ( 1, len - 1 ), b.substr ( 1, len - 1 ) ) + 1 ); if ( a[len - 1] == b[len - 1] ) setMin ( t, minStep ( a.substr ( 0, len - 1 ), b.substr ( 0, len - 1 ) ) + 1 ); return m[hash] = t;
}public: int minReversal ( string init, string goal ) ...{ m.clear (); int res = minStep ( init, goal ); return res == 1 << 20 ? -1 : res; }
};