its_aks_ulure's blog

By its_aks_ulure, history, 5 years ago, In English

I was preparing some problems for a college contest from the past few weeks and came up with this problem idea.

Given N words consisting of either lowercase English letters or a special character '#'. 
Find the expected number of nodes in the trie after a trie is constructed replacing all the special character('#') in the words uniformly randomly with any letter between 'a' to 'z'. 

I want to know if there exists any polynomial time solution for this problem.

Thanks

Full text and comments »

  • Vote: I like it
  • +28
  • Vote: I do not like it