5 ms·

compiling the dictionary into a DFA would give you O(n) runtime.

• behdad 4y ago
  How?
  • jhp123 4y ago
    use a regex like (aardvark|apple|...|zebra)* and the standard DFA construction for regular expressions.
    • behdad 4y ago
      You are technically right. Though if we assume that the size of the dictionary is at least o(n), then the size of such DFA will be exponential in n, and indexing it will be o(n), resulting in a o(n^2) solution again, I think.
      • deleted 4y ago
        [deleted]
      • jhp123 4y ago
        The number of states is exponential for a general regex. This regex has an NFA closely resembling the trie for the dictionary. There could be at most one live state per depth in the trie. So the number of possible states is bounded at least by (words in dictionary)^(length of longest word). Really much smaller because the states at different levels have to share prefixes.
      • ghusbands 4y ago
        They are completely correct. If the DFA fits in RAM, following state transitions will be O(1) and using the DFA for a concatenated string of length N will be O(N). You simply missed a good solution.
    • bonzini 4y ago
      Without the *, you get a graph that is a compressed version of the trie. With the *, the size of the DFA is extremely likely to explode.
• lightbendover 4y ago
  Both the author's and your run-times pretty plainly illustrate everything wrong with BigO.
  • jhp123 4y ago
    ?
• jhp123 4y ago
  actually the trie + dynamic programming solution is also O(n * longest dictionary word) = O(n) ...