找到你要的答案

Q:Reaching from one string to another using given dictionary

Q:使用给定字典从一个字符串到达另一个字符串

For this question, a dictionary was given and two strings also given, it was basically asked to reach from one string to another one just using the words in dictionary, and only one letter can be changed at a time. I came up with this solution. There were some corner cases that my code can not handle. Can you help to find all the corner cases to make this code prettier?

public static int findNumberOfSteps(String start, String end , HashSet<String> dict){

    if( start == null || end == null || dict.isEmpty()){

        throw new IllegalArgumentException();           
    }

    dict.add(end);

    Queue<String> wordHolder = new LinkedList<>(); 
    Queue<Integer> distanceCount = new LinkedList<Integer>();

    wordHolder.add(start);
    distanceCount.add(1);
    int result = Integer.MAX_VALUE;

    while (!wordHolder.isEmpty()){

        String currentWord = wordHolder.poll();
        int currDistance = distanceCount.poll();


        if(currentWord.equals(end)){
            int result = currDistance;
            return result;
        }

        for (int i = 0 ; i < currentWord.length() ; i++){

            char[] charCurrentWord = currentWord.toCharArray();

            for ( char c = 'a' ; c <= 'z' ; c++){

                charCurrentWord[i] = c;

                String newWord = new String(charCurrentWord);


                if (dict.contains(newWord)){

                    wordHolder.add(newWord);
                    distanceCount.add(currDistance+1);
                    dict.remove(newWord);                       
                }                   
            }               
        }           
    }       
    return 0;               
}

对于这个问题,给出了字典,并给出了两个字符串,它基本上要求从一个字符串到另一个只是使用字典中的单词,只有一个字母可以改变一次。我想出了这个解决方案。有一些角落的情况下,我的代码不能处理。你可以找到所有的角落的情况下,为了使代码更漂亮吗?

public static int findNumberOfSteps(String start, String end , HashSet<String> dict){

    if( start == null || end == null || dict.isEmpty()){

        throw new IllegalArgumentException();           
    }

    dict.add(end);

    Queue<String> wordHolder = new LinkedList<>(); 
    Queue<Integer> distanceCount = new LinkedList<Integer>();

    wordHolder.add(start);
    distanceCount.add(1);
    int result = Integer.MAX_VALUE;

    while (!wordHolder.isEmpty()){

        String currentWord = wordHolder.poll();
        int currDistance = distanceCount.poll();


        if(currentWord.equals(end)){
            int result = currDistance;
            return result;
        }

        for (int i = 0 ; i < currentWord.length() ; i++){

            char[] charCurrentWord = currentWord.toCharArray();

            for ( char c = 'a' ; c <= 'z' ; c++){

                charCurrentWord[i] = c;

                String newWord = new String(charCurrentWord);


                if (dict.contains(newWord)){

                    wordHolder.add(newWord);
                    distanceCount.add(currDistance+1);
                    dict.remove(newWord);                       
                }                   
            }               
        }           
    }       
    return 0;               
}
answer1: 回答1:

There are a couple of problems in the code. The first problem is in this code

if(currentWord.equals(end)){
    result = Math.min(result, currDistance);
}

Note that when you reach the end word, that code updates the result, but then the code is going to search for ways to change the end word to something else. That's a huge waste of time, the code should continue with the while(!wordHolder.isEmpy()) loop after the end is found.

The second problem is in this code

if (dict.contains(newWord)){
    wordHolder.add(newWord);
    distanceCount.add(currDistance+1);
    dict.remove(newWord);                       
}   

Note that if newWord is equal to the end word, then that code removes the end word from the dictionary, which means that you'll never find the end word again.

The solution to both problems is to check for the end word inside that if statement. When the end is found, don't add it to the wordHolder and don't remove it from the dictionary.

if (dict.contains(newWord)){
    if(newWord.equals(end)){
        result = Math.min(result, currDistance+1);
    }
    else{
        wordHolder.add(newWord);
        distanceCount.add(currDistance+1);
        dict.remove(newWord);
    }                       
}   

代码中有几个问题。第一个问题是这个代码

if(currentWord.equals(end)){
    result = Math.min(result, currDistance);
}

请注意,当你到达最后一个单词时,该代码会更新结果,但是代码将要搜索改变最终单词到其他东西的方法。这是一个巨大的浪费时间,代码应该继续的同时!wordholder。isempy())结束后循环中被发现。

第二个问题是这个代码

if (dict.contains(newWord)){
    wordHolder.add(newWord);
    distanceCount.add(currDistance+1);
    dict.remove(newWord);                       
}   

注意,如果生词是等于结束的话,那么代码删除从字典中的字,这就意味着你永远不会再找到最后的话。

这两个问题的解决方法是检查if语句中的结束字。当最终发现,不要将它添加到wordholder不要删除它从字典。

if (dict.contains(newWord)){
    if(newWord.equals(end)){
        result = Math.min(result, currDistance+1);
    }
    else{
        wordHolder.add(newWord);
        distanceCount.add(currDistance+1);
        dict.remove(newWord);
    }                       
}   
arrays  algorithm  validation  dictionary  data-structures