• Source 
    1. #include <iostream>
    2. #include <vector>
    3. #include <string>
    4. #include <limits>
    5. using namespace std;
    6.  
    7. class LazyTypist {
    8.     enum class KeyDist {
    9.         q, w, e, r, t, y, u, i, o, p,
    10.         a = 100, s, d, f, g, h, j, k, l,
    11.         left_shift = 200, z, x, c, v, b, n, m, dummy, right_shift,
    12.         space1 = 303, space2, space3, space4, space5
    13.     };
    14.     enum class KeyRaw {
    15.         q, w, e, r, t, y, u, i, o, p,
    16.         a, s, d, f, g, h, j, k, l,
    17.         left_shift, z, x, c, v, b, n, m, dummy, right_shift,
    18.         space1, space2, space3, space4, space5, N_keys
    19.     };
    20.     vector<KeyDist>  RawToDistMap = {
    21.         KeyDist::q, KeyDist::w,KeyDist::e,KeyDist::r,KeyDist::t,KeyDist::y,KeyDist::u,KeyDist::i,KeyDist::o,KeyDist::p,
    22.         KeyDist::a,KeyDist::s,KeyDist::d,KeyDist::f,KeyDist::g,KeyDist::h,KeyDist::j,KeyDist::k,KeyDist::l,
    23.         KeyDist::left_shift,KeyDist::z,KeyDist::x,KeyDist::c,KeyDist::v,KeyDist::b,KeyDist::n,KeyDist::m,KeyDist::dummy,KeyDist::right_shift,
    24.         KeyDist::space1,KeyDist::space2,KeyDist::space3,KeyDist::space4,KeyDist::space5
    25.  
    26.     };
    27.  
    28.     vector<KeyRaw> CharToKeyMap;
    29.  
    30.     vector<int> distance_map;
    31.     vector<int> ResultMap;
    32.     int NKeys;
    33.     int Distance(KeyDist k1, KeyDist k2) {
    34.         return abs(static_cast<int>(k1) % 100 - static_cast<int>(k2) % 100) + abs(static_cast<int>(k1) / 100 - static_cast<int>(k2) / 100);
    35.     }
    36.     int Distance(KeyRaw k1, KeyRaw k2) {
    37.         return abs(static_cast<int>(RawToDistMap[static_cast<int>(k1)]) % 100 - static_cast<int>(RawToDistMap[static_cast<int>(k2)]) % 100) 
    38.             + abs(static_cast<int>(RawToDistMap[static_cast<int>(k1)]) / 100 - static_cast<int>(RawToDistMap[static_cast<int>(k2)]) / 100);
    39.     }
    40.  
    41.     void InitCharToKeyMap() {
    42.         for (int i = 0;i < 65;++i) {
    43.             CharToKeyMap.push_back(KeyRaw::dummy);
    44.         }
    45.         CharToKeyMap.push_back(KeyRaw::a);
    46.         CharToKeyMap.push_back(KeyRaw::b);
    47.         CharToKeyMap.push_back(KeyRaw::c);
    48.         CharToKeyMap.push_back(KeyRaw::d);
    49.         CharToKeyMap.push_back(KeyRaw::e);
    50.         CharToKeyMap.push_back(KeyRaw::f);
    51.         CharToKeyMap.push_back(KeyRaw::g);
    52.         CharToKeyMap.push_back(KeyRaw::h);
    53.         CharToKeyMap.push_back(KeyRaw::i);
    54.         CharToKeyMap.push_back(KeyRaw::j);
    55.         CharToKeyMap.push_back(KeyRaw::k);
    56.         CharToKeyMap.push_back(KeyRaw::l);
    57.         CharToKeyMap.push_back(KeyRaw::m);
    58.         CharToKeyMap.push_back(KeyRaw::n);
    59.         CharToKeyMap.push_back(KeyRaw::o);
    60.         CharToKeyMap.push_back(KeyRaw::p);
    61.         CharToKeyMap.push_back(KeyRaw::q);
    62.         CharToKeyMap.push_back(KeyRaw::r);
    63.         CharToKeyMap.push_back(KeyRaw::s);
    64.         CharToKeyMap.push_back(KeyRaw::t);
    65.         CharToKeyMap.push_back(KeyRaw::u);
    66.         CharToKeyMap.push_back(KeyRaw::v);
    67.         CharToKeyMap.push_back(KeyRaw::w);
    68.         CharToKeyMap.push_back(KeyRaw::x);
    69.         CharToKeyMap.push_back(KeyRaw::y);
    70.         CharToKeyMap.push_back(KeyRaw::z);
    71.         for (int i = 91;i < 97;++i) {
    72.             CharToKeyMap.push_back(KeyRaw::dummy);
    73.         }
    74.         CharToKeyMap.push_back(KeyRaw::a);
    75.         CharToKeyMap.push_back(KeyRaw::b);
    76.         CharToKeyMap.push_back(KeyRaw::c);
    77.         CharToKeyMap.push_back(KeyRaw::d);
    78.         CharToKeyMap.push_back(KeyRaw::e);
    79.         CharToKeyMap.push_back(KeyRaw::f);
    80.         CharToKeyMap.push_back(KeyRaw::g);
    81.         CharToKeyMap.push_back(KeyRaw::h);
    82.         CharToKeyMap.push_back(KeyRaw::i);
    83.         CharToKeyMap.push_back(KeyRaw::j);
    84.         CharToKeyMap.push_back(KeyRaw::k);
    85.         CharToKeyMap.push_back(KeyRaw::l);
    86.         CharToKeyMap.push_back(KeyRaw::m);
    87.         CharToKeyMap.push_back(KeyRaw::n);
    88.         CharToKeyMap.push_back(KeyRaw::o);
    89.         CharToKeyMap.push_back(KeyRaw::p);
    90.         CharToKeyMap.push_back(KeyRaw::q);
    91.         CharToKeyMap.push_back(KeyRaw::r);
    92.         CharToKeyMap.push_back(KeyRaw::s);
    93.         CharToKeyMap.push_back(KeyRaw::t);
    94.         CharToKeyMap.push_back(KeyRaw::u);
    95.         CharToKeyMap.push_back(KeyRaw::v);
    96.         CharToKeyMap.push_back(KeyRaw::w);
    97.         CharToKeyMap.push_back(KeyRaw::x);
    98.         CharToKeyMap.push_back(KeyRaw::y);
    99.         CharToKeyMap.push_back(KeyRaw::z);
    100.     }
    101.  
    102.     int ComputeMinDistance(const string&s, int string_pos, KeyRaw k1, KeyRaw k2) {
    103.         int ik1 = static_cast<int>(k1);
    104.         int ik2 = static_cast<int>(k2);
    105.         int index = NKeys*NKeys*string_pos + NKeys*ik1 + ik2;
    106.         int result = ResultMap[index];
    107.         if (result != -1) return result;
    108.         if (string_pos == 0) {
    109.             ResultMap[index] = 0;
    110.             return 0;
    111.         }
    112.         char c = s[string_pos - 1];
    113.         bool is_possible = false;
    114.         if (c >= 'a' && c <= 'z') {
    115.             KeyRaw newK = CharToKeyMap[c];
    116.             is_possible = k1 == newK || k2 == newK;
    117.         }
    118.  
    119.         if (c >= 'A' && c <= 'Z') {
    120.             KeyRaw newK = CharToKeyMap[c];
    121.             is_possible = ((k1 == KeyRaw::left_shift || k1 == KeyRaw::right_shift) && k2 == newK) ||
    122.                 ((k2 == KeyRaw::left_shift || k2 == KeyRaw::right_shift) && k1 == newK);
    123.         }
    124.         if (c == ' ') {
    125.             is_possible = ( k1 == KeyRaw::space1 || k1 == KeyRaw::space2 || k1 == KeyRaw::space3 || k1 == KeyRaw::space4 || k1 == KeyRaw::space5 ||
    126.                             k2 == KeyRaw::space1 || k2 == KeyRaw::space2 || k2 == KeyRaw::space3 || k2 == KeyRaw::space4 || k2 == KeyRaw::space5);
    127.         }
    128.         result = numeric_limits<int>::max();
    129.         if (is_possible) {
    130.             for (int prev_k1 = 0;prev_k1 < NKeys;++prev_k1) {
    131.                 for (int prev_k2 = 0;prev_k2 < NKeys;++prev_k2) {
    132.                     int prev_res = ComputeMinDistance(s, string_pos - 1, KeyRaw(prev_k1), KeyRaw(prev_k2));
    133.                     if (prev_res == numeric_limits<int>::max()) continue;
    134.                     result = min(result, prev_res + Distance(k1, KeyRaw(prev_k1)) + Distance(k2, KeyRaw(prev_k2)));
    135.                 }
    136.             }
    137.         }
    138.         ResultMap[index] = result;
    139.         return result;
    140.     }
    141.     public:
    142.     int ComputeMinDistance(const string& s) {
    143.         NKeys = static_cast<int>(KeyRaw::N_keys);
    144.         InitCharToKeyMap();
    145.         ResultMap = vector<int>(NKeys * NKeys * (s.length()+1),-1);
    146.         for (int i = 0;i < s.length() + 1;++i) {
    147.             for (int k1 = 0; k1 < NKeys;++k1) {
    148.                 for (int k2 = 0;k2 < NKeys;++k2) {
    149.                     ComputeMinDistance(s, i, KeyRaw(k1), KeyRaw(k2));
    150.                 }
    151.             }
    152.         }
    153.         int result = numeric_limits<int>::max();;
    154.         for (int ik1 = 0;ik1 < NKeys;++ik1) {
    155.             for (int ik2 = 0;ik2 < NKeys;++ik2) {
    156.                 int index = NKeys*NKeys*s.length() + NKeys*ik1 + ik2;
    157.                 result = min(result, ResultMap[index]);
    158.             }
    159.         }
    160.         return result;
    161.     }
    162. };
    163.  
    164. int main() {
    165.  
    166. 	LazyTypist L;
    167. 	string s = "The quick brown fox";
    168. 	cout<<s << ": "<<  L.ComputeMinDistance(s)<<endl;
    169. 	s = "hello world";
    170. 	cout<<s << ": "<<  L.ComputeMinDistance(s)<<endl;
    171. 	s = "qpalzm woskxn";
    172. 	cout<<s << ": "<<  L.ComputeMinDistance(s)<<endl;
    173. 	s = "Hello there DailyProgrammers";
    174. 	cout<<s << ": "<<  L.ComputeMinDistance(s)<<endl;
    175. 	s = "QPgizm QFpRKbi Qycn";
    176. 	cout<<s << ": "<<  L.ComputeMinDistance(s)<<endl;
    177. 	// your code goes here
    178. 	return 0;
    179. }