Dan.Stahr
BAN USER
Comments (4)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
For a single word W, we need
* O(|W|) for counting the letters
* At most O(|W|) for converting it into set (perhaps not needed in other languages, in Python, we can't hash a dictionary)
* O(|W|) on average for looking it up in the set - I think it's safe to assume that we've got a sane implementation of hashtable
Note that set('a', 'b', 'c') is by design equal to set('c', 'b', 'a') and so it holds for the hash codes, which is the only thing that interests us. Internally, frozenset doesn't sort the items anyhow.
For all words, it just sums up to the size of the input.
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Returns the length of the underlying char array, complexity of which is O(1).
- Dan.Stahr April 28, 2014