Commits

Luke Plant committed 71eca4e

Added comment about a more efficient way of using the word tree.

  • Participants
  • Parent commits 4012e7d

Comments (0)

Files changed (1)

File phone2word.hs

 So the algorithm is:
 
  - find all the 'word logs'
-   - necessarily an O(n^2) algorithm, assuming we can check a
-     string of digits in constant time
+   - looking up a single sequence of digits in the wordTree
+     is O(1), since the wordTree has a fixed depth defined by
+     the dictionary.
+
+   - here we use an O(n^2) algorithm to find sub-sequences
+     of the original digits, so it is O(n^2) overall.
+
+   - we could use an algorithm that looks up a sequence of
+     digits *and* all the prefixes of that sequence in a
+     single pass through the wordTree, which would allow
+     us to find all the words in the digit sequence in O(n)
+     time. But it isn't the limiting factor.
+
  - add in all necessary 'digit logs'
    - depends on the number and spacing of word logs
  - find all routes across the river