Skip to main content
deleted 5 characters in body
Source Link
janos
  • 113.1k
  • 15
  • 154
  • 396

First of all, I really liked that your logic doesn't need to compare lengths: as soon as a match is found, it must be one of the shortest lengths, nice! And when the end is unreachable, the method returns 0, an impossible answer (since a valid length must be >= 1), so that's good too.

A couple of things can be improved.


ChoosingChoose the right interfaces

Your method should work with Set<String> dict, and should not limit users to HashSet<String> dict.

ChoosingChoose the right classes

A Deque is a collection that supports element insertion and removal at both ends. That's more than what you need. A Stack would have been enough for your purpose.

SimplifyingSimplify the inner forfor loops

The inner for loops are a bit wasteful and can be simplified. You are basically iterating over all possible 1-letter differences and check if in the dictionary. Instead, you could iterate elements of the dictionary and see if they have 1 letter difference. For example like this:

for (String item : dict.toArray(new String[dict.size()])) {
    if (isSingleCharDiff(analyzing, item)) {
        dict.remove(item);
        lengthCount.add(curCount + 1);
        wordSearch.add(item);
    }
}

Discrepancy with the specs

The problem description says:

dict = ["hot","dot","dog","lot","log"]

With this exact input your method returns 0 because it will never reach end. The fix is simple enough, just add it to the dictionary somewhere near the start:

dict.add(end);

A wasted operation

Before the while loop, you do this:

wordSearch.add(start);
lengthCount.add(1);

but then inside the loop you immediately pop them. You could rework the code to eliminate that wasted operation:

String analyzing = start;
int curCount = 1;
while (true) {
    if (analyzing.equals(end)) {
        return curCount;
    }
    for (String item : dict.toArray(new String[dict.size()])) {
        if (isSingleCharDiff(analyzing, item)) {
            dict.remove(item);
            lengthCount.add(curCount + 1);
            wordSearch.add(item);
        }
    }
    if (wordSearch.isEmpty()) {
        break;
    }
    analyzing = wordSearch.pop();
    curCount = lengthCount.pop();
}

First of all, I really liked that your logic doesn't need to compare lengths: as soon as a match is found, it must be one of the shortest lengths, nice! And when the end is unreachable, the method returns 0, an impossible answer (since a valid length must be >= 1), so that's good too.

A couple of things can be improved.


Choosing the right interfaces

Your method should work with Set<String> dict, and should not limit users to HashSet<String> dict.

Choosing the right classes

A Deque is a collection that supports element insertion and removal at both ends. That's more than what you need. A Stack would have been enough for your purpose.

Simplifying the inner for loops

The inner for loops are a bit wasteful and can be simplified. You are basically iterating over all possible 1-letter differences and check if in the dictionary. Instead, you could iterate elements of the dictionary and see if they have 1 letter difference. For example like this:

for (String item : dict.toArray(new String[dict.size()])) {
    if (isSingleCharDiff(analyzing, item)) {
        dict.remove(item);
        lengthCount.add(curCount + 1);
        wordSearch.add(item);
    }
}

Discrepancy with the specs

The problem description says:

dict = ["hot","dot","dog","lot","log"]

With this exact input your method returns 0 because it will never reach end. The fix is simple enough, just add it to the dictionary somewhere near the start:

dict.add(end);

A wasted operation

Before the while loop, you do this:

wordSearch.add(start);
lengthCount.add(1);

but then inside the loop you immediately pop them. You could rework the code to eliminate that wasted operation:

String analyzing = start;
int curCount = 1;
while (true) {
    if (analyzing.equals(end)) {
        return curCount;
    }
    for (String item : dict.toArray(new String[dict.size()])) {
        if (isSingleCharDiff(analyzing, item)) {
            dict.remove(item);
            lengthCount.add(curCount + 1);
            wordSearch.add(item);
        }
    }
    if (wordSearch.isEmpty()) {
        break;
    }
    analyzing = wordSearch.pop();
    curCount = lengthCount.pop();
}

First of all, I really liked that your logic doesn't need to compare lengths: as soon as a match is found, it must be one of the shortest lengths, nice! And when the end is unreachable, the method returns 0, an impossible answer (since a valid length must be >= 1), so that's good too.

A couple of things can be improved.


Choose the right interfaces

Your method should work with Set<String> dict, and should not limit users to HashSet<String> dict.

Choose the right classes

A Deque is a collection that supports element insertion and removal at both ends. That's more than what you need. A Stack would have been enough for your purpose.

Simplify the inner for loops

The inner for loops are a bit wasteful and can be simplified. You are basically iterating over all possible 1-letter differences and check if in the dictionary. Instead, you could iterate elements of the dictionary and see if they have 1 letter difference. For example like this:

for (String item : dict.toArray(new String[dict.size()])) {
    if (isSingleCharDiff(analyzing, item)) {
        dict.remove(item);
        lengthCount.add(curCount + 1);
        wordSearch.add(item);
    }
}

Discrepancy with the specs

The problem description says:

dict = ["hot","dot","dog","lot","log"]

With this exact input your method returns 0 because it will never reach end. The fix is simple enough, just add it to the dictionary somewhere near the start:

dict.add(end);

A wasted operation

Before the while loop, you do this:

wordSearch.add(start);
lengthCount.add(1);

but then inside the loop you immediately pop them. You could rework the code to eliminate that wasted operation:

String analyzing = start;
int curCount = 1;
while (true) {
    if (analyzing.equals(end)) {
        return curCount;
    }
    for (String item : dict.toArray(new String[dict.size()])) {
        if (isSingleCharDiff(analyzing, item)) {
            dict.remove(item);
            lengthCount.add(curCount + 1);
            wordSearch.add(item);
        }
    }
    if (wordSearch.isEmpty()) {
        break;
    }
    analyzing = wordSearch.pop();
    curCount = lengthCount.pop();
}
Source Link
janos
  • 113.1k
  • 15
  • 154
  • 396

First of all, I really liked that your logic doesn't need to compare lengths: as soon as a match is found, it must be one of the shortest lengths, nice! And when the end is unreachable, the method returns 0, an impossible answer (since a valid length must be >= 1), so that's good too.

A couple of things can be improved.


Choosing the right interfaces

Your method should work with Set<String> dict, and should not limit users to HashSet<String> dict.

Choosing the right classes

A Deque is a collection that supports element insertion and removal at both ends. That's more than what you need. A Stack would have been enough for your purpose.

Simplifying the inner for loops

The inner for loops are a bit wasteful and can be simplified. You are basically iterating over all possible 1-letter differences and check if in the dictionary. Instead, you could iterate elements of the dictionary and see if they have 1 letter difference. For example like this:

for (String item : dict.toArray(new String[dict.size()])) {
    if (isSingleCharDiff(analyzing, item)) {
        dict.remove(item);
        lengthCount.add(curCount + 1);
        wordSearch.add(item);
    }
}

Discrepancy with the specs

The problem description says:

dict = ["hot","dot","dog","lot","log"]

With this exact input your method returns 0 because it will never reach end. The fix is simple enough, just add it to the dictionary somewhere near the start:

dict.add(end);

A wasted operation

Before the while loop, you do this:

wordSearch.add(start);
lengthCount.add(1);

but then inside the loop you immediately pop them. You could rework the code to eliminate that wasted operation:

String analyzing = start;
int curCount = 1;
while (true) {
    if (analyzing.equals(end)) {
        return curCount;
    }
    for (String item : dict.toArray(new String[dict.size()])) {
        if (isSingleCharDiff(analyzing, item)) {
            dict.remove(item);
            lengthCount.add(curCount + 1);
            wordSearch.add(item);
        }
    }
    if (wordSearch.isEmpty()) {
        break;
    }
    analyzing = wordSearch.pop();
    curCount = lengthCount.pop();
}