# Time complexity of transforming one string to another

Here is the problem:

Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine if $s$ produces $t$. If it does produce $t$, output the length of of the shortest production sequence, otherwise, output $-1$.

Example: $D$ = [bat, cot, dog, dag, dot, cat], $s$ = cat, $t$ = dog, the shortest production sequence would be [cat, cot, dot, dog], giving us an output of four.

Here is the algorithm (Breadth First Search):

private static class StringWithDistance {
public String candidateString;
public Integer distance;

public StringWithDistance(String candidateString, Integer distance) {
this.candateString = candidateString;
this.distance = distance;
}
}

public static int transformString(Set<String> D, String s, String t) {
Set<String> visited = new HashSet<String>(D);
Queue<StringWithDistance> q = new ArrayDequeu<>();
visited.remove(s) // mark as visited by erasing it

stringWithDistance f;
while ((f = q.poll()) != null) {
if (f.candidateString.equals(t)) {
return f.distance;
}

for (int i = 0; i < str.length(); ++i) {
String strStart = i == 0 ? "" : str.substring(0, i);
String strEnd = i + 1 < str.length() ? str.substring(i + 1) : "";
for (int c = 0; c < 26; ++c) {
String modStr = strStart + (char)('a' + c) + strEnd;
if (visited.contains(modStr)) {
visited.remove(modStr);
}
}
}
}


I'm having a hard time understanding why this algorithm is $O(n^2)$. I know that the time complexity of processing the vertices/words is $O(n)$, but based on the text I'm reading, processing the edges in the worst case would be $O(n^2)$, so we would have $O(n + n^2)$, giving us $O(n^2)$.

I just can't see how that is taking place. The second loop is a constant (right?), it doesn't change with the size of $n$, so I don't think that is a part of the calculation for the run time.

Any help would be greatly appreciated.

• What do you mean by "produce"? Jul 14 '18 at 5:05
• @mitchric, can you tell us where to find "the text I'm reading" that say "processing the edges in the worst case would be O(n^2)"? I am planning to argue in your favor against that text. I suspect either that text mistakenly thinks the operations on a HashSet of size n in the worst case is O(n) or it does not take into account of an algorithm that uses HashSet. Aug 7 '18 at 6:37
• @Apass.Jack I pulled this problem from Elements of Programming Interviews in Java by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. Aug 7 '18 at 13:43

As told by OP, the problem and its the solution come from Elements of Programming Interviews in Java by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

Here is the excerpt of the book that analyzes the time-complexity of the solution.

The number of vertices is the number d of words in the dictionary. The number of edges is, in the worst-case, $O(d^2)$. The time complexity is that of BFS, namely $O(d + d^2) = O(d^2)$. If the string length $n$ is less than $d$ then the maximum number of edges out of a vertex is $O(n)$, implying an $O(nd)$ bound.

The above analysis in the book is correct. Please note "word" and "string" are used interchangeably here.

Here is OP's analysis, with the only modification that I use $d$ to denote the number of words so as to be consistent with the book.

The second loop is a constant (right?), it doesn't change with the size of $d$, so I don't think that is a part of the calculation for the run time.

OP's analysis is not wrong, either, if we assume that the length of the strings in the dictionary is bounded by a constant. This assumption is not unreasonable since it conforms to our ordinary experience about words in a normal dictionary. In fact, OP's analysis has been included in the book as well! It is the very last statement of the excerpt above.

Is there a logical inconsistency between the bounds $O(d^2)$ and $O(nd)$? No, since they apply to different situations with different assumptions. For example, in the worst case where every string differ in exactly one character with every other string, if we let $d$ go to infinity, then the maximal string length $n$ will goes to infinity as well. That is, "The second loop" does "change with the size of $d$"! Those strings are very unlikely to be words in our ordinary dictionary because of their huge lengths, of course.

In fact, in all cases, $d \leq 26n$. So $O(d^2)$ implies $O(nd)$.