its_aks_ulure's blog

By its_aks_ulure, history, 13 months ago,

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