记忆化搜索,类似邮局问题的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] =......
阅读全文