# Commits

committed 71eca4e

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

• Participants
• Parent commits 4012e7d
• Branches default

# 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`