0

i run this program and it gives the runtime error

" Runtime error: exit code is -1073741819 ".

can someone plz tell me why tis error occurs and how to rectify it?

the program is finding the word ladder (length of the shortest chain to reach the target word) . i.e Given a dictionary, and two words ‘start’ and ‘target’ (both of same length). Find length of the smallest chain from ‘start’ to ‘target’ if it exists, such that adjacent words in the chain only differ by one character and each word in the chain is a valid word i.e., it exists in the dictionary. It may be assumed that the ‘target’ word exists in dictionary and length of all dictionary words is same.

#include<bits/stdc++.h> using namespace std; string dic[] = {"POON", "PLEE", "SAME", "POIE", "PLEA", "PLIE", "POIN"}; int n = sizeof(dic)/sizeof(dic[0]); set<string> graph; struct word { string s; int d; }; bool isAdj(string &s , string &t) { int count = 0; for(int i=0; i<s.length() && i<t.length(); i++) if(s[i] != t[i]) count++; return (count == 1); } int shortestPath(string s , string d) { queue<word> que; word source = {s , 0}; que.push(source); word cur; //string t = "PLEA"; while(!que.empty()) { cur = que.front(); if(cur.s == d) break; for(string t : graph) { if(isAdj(cur.s , t)) { word temp = {t, cur.d + 1}; que.push(temp); graph.erase(t); } } que.pop(); } if(cur.s == d) return cur.d; return 0; } main() { for(int i=0; i<n; i++) graph.insert(dic[i]); cout<<" "<<shortestPath("TOON" , "PLEA") ; }

the question link is here http://www.geeksforgeeks.org/word-ladder-length-of-shortest-chain-to-reach-a-target-word/

thanks in advance.

Improve this question
4
  • 3
    Don't use ranged-for on a collection you modify during enumeration. Commented May 3, 2017 at 6:04
  • but even if i use for(auto it = graph.begin(); it != graph.end(); it++) , the same runtime error is coming. Commented May 3, 2017 at 8:05
  • 3
    i linked that answer for a reason, and you would do well to read the selected answer. What you're doing is still wrong. Look closely at the proper example of how to perform iterator based enumeration with potential container item erasure in the selected answer of the question I posted. There should be no increment-statement in the for-loop construct. there will be an erase or an increment within the body of the loop. Better still, recode it as a while and mimic the linked behavior. Commented May 3, 2017 at 8:18
  • yeah worked. Thanks Commented May 3, 2017 at 17:45

1 Answer 1

Reset to default
0

The comments have a major good point.

However, it misses another issue - you don't have to edit the graph in that loop.

list<string> foundStrings; for(string t : graph) { if(isAdj(cur.s , t)) { foundStrings.push_back(t); } } for(string t: foundStrings) { word temp = {t, cur.d + 1}; que.push(temp); graph.erase(t); }

(There should probably be some error handling as well.)

Basically: If you are changing a sequence while you are iterating over it you have to take extra pre-cautions and cannot use C++11 style, but the best option is to not modify it at that time - the second option is to use iterators and take special care.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

The OP's code finds multiple "adjacent" strings, and queues all of them. Your code only uses the last (or first with the break) it finds. depending on the order the OP's example goes into the set, it won't find the depth.
I changed the answer to handle multiple matches.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.