Confuse with 18.7 Transform one string to another

#1

For this question, are we assume all the words in the dictionary initially has distance 0 and assume t is not in the dictionary?

if (! visited.contains(modStr)) {
  visited.add(modStr);
  q.add(new StringWithDistance(modStr, f.distance + 1);
}

I am a bit confused in here, inside of BFS we are only adding the word to the queue that not in the dictionary. But are we suppose to find the distance within the dictionary?

0 Likes
#2

Hi @Hitchcock,

There is a small confusion here, and we recently refactored the code to make it more understandable. You might take a look as follows:

   // Uses BFS to find the least steps of transformation.
   public static int transformString(Set<String> D, String s, String t) {
     Set<String> visited = new HashSet<String>(D);
     Queue<StringWithDistance> q = new LinkedList<>();
     visited.remove(s); // Marks s as visited by erasing it.
     q.add(new StringWithDistance(s, 0));
 
     StringWithDistance f;
     while ((f = q.poll()) != null) {
       // Returns if we find a match.
       if (f.candidateString.equals(t)) {
         return f.distance; // Number of steps reaches t.
       }
 
       // Tries all possible transformations of f.candidateString.
       String str = f.candidateString;
       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) { // Iterates through 'a' ~ 'z'.
           String modStr = strStart + (char)('a' + c) + strEnd;
           if (visited.contains(modStr)) {
             visited.add(modStr);
             q.add(new StringWithDistance(modStr, f.distance + 1));
           }
         }
       }
     }
 
     return -1; // Cannot find a possible transformations.
   }

Let us know if you have any other question.

0 Likes
#3

Just a little bit issue I found.

           if (visited.contains(modStr)) {
             visited.add(modStr);
             q.add(new StringWithDistance(modStr, f.distance + 1));
           }

Does it suppose to change visited.add(modStr) to visited.remove(modStr) ?

0 Likes
#4

Hi @Hitchcock,

Yes, you are right, this shall be visited.remove(modStr) there. Really appreciate your double-checking!

0 Likes