Much better than OPs solution ;) but time and space requirements for the data preparation is still O(n). much more than 0(m * log(n)) and O(m), respectively (once again, for sorted dictionaries only).

So if dictionary is unsorted, the memory requirements are not a problem and if this task is not often repeated, yours is the best solution IMHO.