Same algorithm in C++ gave me running time error


  • 1
    F

    Here is accepted code in Java found on line:

    public class Solution {
        public int ladderLength(String start, String end, Set<String> dict) {
                if (dict == null || dict.size() == 0) {
            return 0;
        }
     
        Queue<String> wordsQ = new LinkedList<String>();
        Queue<Integer> levelsQ = new LinkedList<Integer>();
        wordsQ.add(start);
        levelsQ.add(1);
        while (!wordsQ.isEmpty()) {
            // String in Java is immutable, so use StringBuilder
            StringBuilder word = new StringBuilder(wordsQ.poll());
            int level = levelsQ.poll();
     
            for (int i = 0; i < word.length(); i++) {
                char tmpChar = word.charAt(i);
                for (char j = 'a'; j <= 'z'; j ++) {
                    word.setCharAt(i, j);
                    String temp = word.toString();
                    if (temp.equals(end)) {
                        return level + 1;
                    }
                    if (dict.contains(temp)) {
                        wordsQ.add(temp);
                        levelsQ.add(level + 1);
                        dict.remove(temp);
                    }
                }
                word.setCharAt(i, tmpChar);
            }
        }
        return 0;
        }
    }
    

    I translated it into C++:

    class Solution {
    public:
        int ladderLength(string start, string end, unordered_set<string> &dict) {
            if (start.length() != end.length() || start.length() == 0 || dict.size() == 0)
               return 0;
            queue<string> wordQ;
            queue<int> levelQ;
            wordQ.push(start);
            levelQ.push(1);
            while (!wordQ.empty()) {
                string word = wordQ.front();
                wordQ.pop();
                int level = levelQ.front();
                wordQ.pop();
                for (int i = 0; i < word.length(); i++) {
                    char tmpChar = word[i];
                    for (char j = 'a'; j <= 'z'; j++) {
                        word[i] = j;
                        if (word == end)
                           return level + 1;
                        if (dict.count(word)) {
                           wordQ.push(word);
                           levelQ.push(level + 1);
                           dict.erase(word);
                         }
                    }
                    word[i] = tmpChar;
                }
            }
        return 0;
        }
    };
    

    and OJ gave me a running time error:
    Last executed input: "a", "c", ["a","b","c"]

    Can you tell why? Thanks.


  • 2
    M

    change

     int level = levelQ.front();
     wordQ.pop();
    

    to

    int level = levelQ.front();
    levelQ.pop();
    

  • 0
    F

    Thanks a lot!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.