1
$\begingroup$

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
    q.add(new StringWithDistance(s, 0);

    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);
                   q.add(new StringWithDistance(f, f.distance + 1);
               }
            }
        }
    }

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.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "produce"? $\endgroup$ – xskxzr Jul 14 '18 at 5:05
  • $\begingroup$ @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. $\endgroup$ – Apass.Jack Aug 7 '18 at 6:37
  • $\begingroup$ @Apass.Jack I pulled this problem from Elements of Programming Interviews in Java by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. $\endgroup$ – mitchric Aug 7 '18 at 13:43
2
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.