Word Ladder accepted a wrong answer (test case need to be improved)


  • 1
    H
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        if (start == end) return 1;
        map<string, int> m;
        queue<string> q;
        q.push(start);
        m[start] = 1;
        while(!q.empty()) {
          string src = q.front();
          q.pop();
          // if (src == end) {
          //   return m[src];
          // }
          char tmp;
          int level = m[src]+1;
          for (int i=0;i<src.size();i++) {
            string tmp = src;
            for (char c='a';c<='z';c++) {
              tmp[i] = c;
              // if (tmp == end) {
              //   return level;
              // }
              if (m.count(tmp) == 0 && dict.count(tmp)>0 ) {
                q.push(tmp);
                m[tmp] = level;
              }
            }
          }
        }
        return 0;
      }
    

    As you can see, if I uncomment one of the return statements which is commented out, both of them can be accepted.
    However, only the second one should be accepted.

    The reason is, the dict will not necessarily contain end. So end will not be inserted into q. Thus the first return clause couldn't be executed.

    On my machine, it fails as I thought, but it is accepted by the OJ.


  • 0

    Could you please describe the test case you used? Thanks.


  • 0
    H

    Just the example in the problem it self.
    Given:
    start = "hit"
    end = "cog"
    dict = ["hot","dot","dog","lot","log"]


  • 0
    G

    +1 need to add the example case to OJ

    start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]
    

    Otherwise wrong solution could pass the OJ, e.g. this one:
    https://github.com/yuzhangcmu/Python-Study/blob/master/Leetcode/Word_Ladder.py


Log in to reply
 

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