Complexity of 19.8 (Find string transformation)

#1

Hello,
I would like to share several questions and thoughts on problem to problem 19.8 (Find string transformation).

Should I include the max length of strings into the complexity of the solution? For each string of maximum n characters (each vertex), we need to compute all O(26 * n) = O(n) 1-character mutations. Therefore, the complexity becomes O(n * d), where d is the dictionary size (there are d words, each word needs O(n) computation). The book indeed explains that when n < d, the complexity becomes O(nd) because the number of edges drop to n. However, I think the complexity is still O(nd) even when we have a short dictionary and long strings (i.e., n >= d)

Also, although it depends on implementation, computing a hash is typically linear to length of string. Therefore, the complexity can be O(n * n * d) if we count the hashing computation costs. Do you think so?

Moreover, I guess a more efficient way for finding adjacent strings is to build a prefix tree from the dictionary.

0 Likes
#2

I think the main question here is that do you consider the hash function cost into account or not. Most of time, people don’t consider that because as follows:

  • Hash function may not read the whole string to compute the hash code. For example, you might just decide a hash code based on the first few characters of the string.
  • This kind of operations are very implementation specific and if you really want to discuss complexity in a complete way. You might want to discuss this in bit-complexity level.

Please let me know if you have any problem.

0 Likes
#3

Thank you for the detailed answer. I also think that the hash functions should be considered O(1) in general because they are implementation specific.

However, I still have an argument that we still need to consider all one-character mutations even when the dictionary size is small. That means we always need to compute and find hashes of O(26 * n) = O(n) mutations for each word of length n in the dictionary. Therefore, the complexity of the solution is O(n * d) where n is the max length of words. For example, if dictionary is {“abcde”, “abcdf”, “abcff”}, source string is “abcde” and destination string is “abcff”, the algorithm will take a time linear to length of strings. (According to the book, it will take O(d^2) because the length of string is greater than the dictionary size.)

0 Likes